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 <= 1000To solve #2470 Number of Subarrays With LCM Equal to K, the key idea is to explore all subarrays and maintain the LCM (Least Common Multiple) as the subarray expands. Start each subarray at index i and iteratively include elements to the right while updating the running LCM using lcm(a, b) = (a * b) / gcd(a, b). If the LCM becomes greater than k or k % currentLCM != 0, the subarray can no longer produce the desired value, so you can stop expanding that window early.
Each time the running LCM becomes exactly k, increment the count of valid subarrays. The pruning condition significantly reduces unnecessary computations because only numbers that divide k can contribute to a valid LCM. This approach leverages number theory properties and efficient gcd calculations to keep updates fast.
Although the naive exploration is quadratic, early termination often improves practical performance. The approach mainly requires iterative scanning with minimal additional storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Subarray Expansion with Running LCM and Pruning | O(n^2 log k) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The constraints on nums.length are small. It is possible to check every subarray.
To calculate LCM, you can use a built-in function or the formula lcm(a, b) = a * b / gcd(a, b).
As you calculate the LCM of more numbers, it can only become greater. Once it becomes greater than k, you know that any larger subarrays containing all the current elements will not work.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
If the current LCM does not divide k, adding more numbers can only increase or keep the LCM the same but will never transform it into exactly k. This observation allows early termination of the inner loop and reduces unnecessary computation.
Problems involving LCM, GCD, and subarray enumeration appear in coding interviews because they test number theory and optimization skills. Variants of this question can appear in interviews at large tech companies and competitive coding platforms.
This problem mainly relies on mathematical operations rather than complex data structures. A simple loop with integer variables for tracking the running LCM and using the gcd function is sufficient to efficiently compute results.
The common approach is to iterate over each starting index and expand the subarray while maintaining the running LCM using the gcd formula. If the LCM exceeds k or no longer divides k, the expansion stops early. Each time the LCM equals k, the subarray count increases.