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.
This is a straightforward method to solve the problem by calculating the GCD for every possible subarray in the given list and checking if it equals k. Although not the most efficient, it works within the constraints.
The C solution iterates over all possible subarrays and calculates the GCD of elements using a helper function. Whenever the current GCD matches k, it increments the count. We break the inner loop if the current GCD becomes less than k to optimize unnecessary checks.
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach leverages properties of GCD to reduce unnecessary calculations. Given that the GCD can only decrease or remain the same when expanding a subarray, the inner loop can stop early when the current GCD drops below k, further enhancing efficiency.
In the C optimized solution, we start by checking if the current number is divisible by k before computing the GCD. This eliminates unnecessary calculations and checks subarrays beginning only with potential contributors to valid GCD.
Time Complexity: O(n^2), but faster due to early exits
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using GCD Properties | Time Complexity: O(n^2), but faster due to early exits |
| 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. |
2447. Number of Subarrays With GCD Equal to K | Leetcode Weekly 316 | LeetCode 2447 • Bro Coders • 2,455 views views
Watch 9 more video solutions →Practice Number of Subarrays With GCD Equal to K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor