Given an integer array nums and an integer k, return the number of subarrays of nums where the greatest common divisor of the subarray's elements is k.
A subarray is a contiguous non-empty sequence of elements within an array.
The greatest common divisor of an array is the largest integer that evenly divides all the array elements.
Example 1:
Input: nums = [9,3,1,2,6,3], k = 3 Output: 4 Explanation: The subarrays of nums where 3 is the greatest common divisor of all the subarray's elements are: - [9,3,1,2,6,3] - [9,3,1,2,6,3] - [9,3,1,2,6,3] - [9,3,1,2,6,3]
Example 2:
Input: nums = [4], k = 7 Output: 0 Explanation: There are no subarrays of nums where 7 is the greatest common divisor of all the subarray's elements.
Constraints:
1 <= nums.length <= 10001 <= nums[i], k <= 109The key idea for solving Number of Subarrays With GCD Equal to K is understanding how the gcd of a subarray changes as the subarray grows. For each starting index, you can progressively extend the subarray and update the running gcd. Since the gcd value can only stay the same or decrease when adding elements, many branches can be pruned early if the value becomes smaller than k or is no longer divisible by k.
A common optimization is to maintain the current GCD while expanding the subarray and count whenever it becomes exactly k. Another efficient perspective uses a map to track the frequency of GCD values for subarrays ending at the current index, reducing redundant recomputation.
This approach leverages properties of number theory and the Euclidean algorithm. With pruning or GCD frequency tracking, the algorithm performs efficiently for typical constraints with about O(n log A) GCD operations, where A is the maximum element.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Expand subarray with running GCD | O(n^2 log A) | O(1) |
| GCD frequency map optimization | O(n log A) | O(log A) |
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 GCD, you can use a built-in function or the Euclidean Algorithm.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
When you extend a subarray, the GCD can only remain the same or decrease. If the GCD becomes smaller than k or is not divisible by k, it can never become k again for that subarray extension. This property allows early termination of many iterations.
A hash map or dictionary is often used to store the count of GCD values for subarrays ending at the current index. This allows merging results from previous computations and prevents recalculating GCDs for all possible subarrays.
Problems involving subarray properties with GCD or number theory concepts do appear in technical interviews. Variants of this problem test knowledge of arrays, mathematical properties, and optimization techniques, which are common in FAANG-style interviews.
An efficient approach keeps track of the GCD of subarrays ending at each index. By updating GCD values incrementally and counting when the result equals k, you avoid recomputing GCDs from scratch. This reduces the effective complexity to around O(n log A).