Given an integer array nums and an integer k, return the number of subarrays of nums where the least common multiple of the subarray's elements is k.
A subarray is a contiguous non-empty sequence of elements within an array.
The least common multiple of an array is the smallest positive integer that is divisible by all the array elements.
Example 1:
Input: nums = [3,6,2,7,1], k = 6 Output: 4 Explanation: The subarrays of nums where 6 is the least common multiple of all the subarray's elements are: - [3,6,2,7,1] - [3,6,2,7,1] - [3,6,2,7,1] - [3,6,2,7,1]
Example 2:
Input: nums = [3], k = 2 Output: 0 Explanation: There are no subarrays of nums where 2 is the least common multiple of all the subarray's elements.
Constraints:
1 <= nums.length <= 10001 <= nums[i], k <= 1000Problem Overview: You are given an integer array nums and an integer k. The task is to count how many contiguous subarrays have a Least Common Multiple (LCM) exactly equal to k. A subarray contributes to the answer only if the LCM of all its elements equals k.
Approach 1: Brute Force Enumeration (O(n² log k) time, O(1) space)
Start every subarray from index i and extend it to the right. Maintain the running LCM while iterating j from i to n-1. The LCM of two numbers is computed using lcm(a,b) = (a * b) / gcd(a,b). Each time the running LCM becomes exactly k, increment the answer. If the LCM exceeds k or k % currentLCM != 0, further expansion cannot produce k, so you stop early for that starting index. This direct enumeration checks all possible subarrays and works well for small inputs.
Approach 2: Optimized Expansion with Prefix LCM Pruning (O(n log k) time, O(1) space)
The key observation: if the current LCM ever becomes greater than k or is not a divisor of k, extending the subarray will never bring it back to k. Use the same outer loop for starting index i, but aggressively prune expansions based on this property. Maintain a running LCM while extending the subarray and stop immediately once the divisor condition fails. Because LCM values grow quickly, the inner loop usually runs only a few iterations, making the practical complexity close to linear. All LCM calculations rely on fast gcd operations from number theory.
This approach leverages properties of math and number theory to avoid exploring impossible states. The array itself is processed sequentially using simple iteration patterns common in array problems.
Recommended for interviews: Interviewers expect the optimized expansion approach. The brute force method demonstrates that you understand how to compute LCM incrementally across subarrays. The optimized version shows deeper insight into number theory constraints, specifically the observation that valid LCMs must divide k. That pruning reduces unnecessary checks and brings the complexity close to O(n log k), which is typically the intended solution.
This approach involves iterating over all possible subarrays, calculating the Least Common Multiple (LCM) for each, and checking if it equals k. Though this is a straightforward way to tackle the problem, it is not the most efficient.
The code employs a double loop to iterate through all the subarrays. For each subarray, it calculates the LCM of its elements and checks if it equals the given number k. Whenever the LCM matches k, it increments the result count. The greatest common divisor (GCD) function is used to calculate the LCM efficiently.
The time complexity of this approach is O(n^2) due to the double loop iterating over subarrays. The space complexity is O(1), as no additional space proportional to input size is used.
This approach involves using a prefix LCM concept to optimize the calculation of LCM over subarrays. By storing intermediate LCM values, we can reduce redundant computations, potentially yielding a more efficient solution.
This C implementation optimizes the LCM computation by maintaining a prefix array where the LCM up to each index is stored and reused for further calculations. This reduces the need to recompute LCMs from scratch for every potential subarray.
The approach improves the effective time complexity compared to the brute force method by using previously computed values, potentially avoiding some redundant calculations. The space complexity is O(n) due to the prefix array.
Enumerate each number as the first number of the subarray, and then enumerate each number as the last number of the subarray. Calculate the least common multiple of this subarray. If the least common multiple equals k, then increment the answer by one.
The time complexity is O(n^2). Here, n is the length of the array.
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity of this approach is O(n^2) due to the double loop iterating over subarrays. The space complexity is O(1), as no additional space proportional to input size is used. |
| Optimized Approach Using Prefix LCM | The approach improves the effective time complexity compared to the brute force method by using previously computed values, potentially avoiding some redundant calculations. The space complexity is O(n) due to the prefix array. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n² log k) | O(1) | When constraints are small or when demonstrating the baseline logic for computing LCM across subarrays. |
| Optimized Prefix LCM Expansion with Pruning | O(n log k) | O(1) | General case and interview solution. Stops early when LCM exceeds k or stops dividing k. |
2470. Number of Subarrays With LCM Equal to K | LeetCode Weekly Contest 319 | LeetCode 2471 • Bro Coders • 2,283 views views
Watch 9 more video solutions →Practice Number of Subarrays With LCM Equal to K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor