Watch 10 video solutions for Number of Subarrays With GCD Equal to K, a medium level problem involving Array, Math, Number Theory. This walkthrough by Bro Coders has 2,455 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: Given an integer array nums and an integer k, count how many contiguous subarrays have a greatest common divisor (GCD) exactly equal to k. The challenge is that every subarray has its own GCD, so a naive enumeration quickly becomes expensive for larger arrays.
Approach 1: Brute Force with Incremental GCD (O(n² log M) time, O(1) space)
Iterate over every possible starting index and extend the subarray one element at a time. Maintain a running gcd value using the current element and the previous GCD. Each time you extend the subarray, compute gcd(currentGCD, nums[j]). If the result equals k, increment the count. If the GCD drops below k or becomes a value that cannot reach k, you can stop extending that subarray. The main work comes from repeatedly computing GCD values, which costs O(log M) where M is the maximum number in the array. This approach directly demonstrates how GCD evolves as a subarray grows.
This method relies heavily on properties of the Euclidean algorithm from number theory. While simple to implement, the nested loops make it quadratic in the worst case, which may be borderline for large inputs.
Approach 2: Optimized Using GCD Compression (O(n log M) time, O(log M) space)
A key observation: the number of distinct GCD values for subarrays ending at a fixed index is small. Instead of recomputing every subarray independently, maintain a collection of pairs representing (gcd value, frequency) for all subarrays ending at the previous index. For the current element, compute new GCDs by combining nums[i] with each previous GCD and merging identical results.
This effectively compresses multiple subarrays that share the same GCD into one entry. Each step produces only a limited set of distinct GCDs, so the total work stays around O(n log M). Whenever a computed GCD equals k, add its frequency to the answer.
The algorithm processes the array once and repeatedly applies the Euclidean GCD operation, making it a strong mix of array traversal and math reasoning. It avoids exploring every possible subarray explicitly.
Recommended for interviews: Start with the brute force idea to show you understand how subarray GCDs evolve. Then move to the optimized GCD-compression technique. Interviewers typically expect the optimized approach because it demonstrates deeper knowledge of GCD properties and how to reduce repeated work across overlapping subarrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Incremental GCD | O(n² log M) | O(1) | Good for understanding GCD behavior in subarrays or when input size is small. |
| Optimized GCD Compression | O(n log M) | O(log M) | Best general solution. Efficient for large arrays by reusing GCD results from previous subarrays. |