Number of Subarrays With GCD Equal to K
MedPrompt
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 <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to generate all possible contiguous subarrays, calculate the greatest common divisor (GCD) for each one, and count how many of them have a GCD equal to k.
We can use two nested loops to define the start and end of each subarray. The outer loop fixes the starting element, and the inner loop expands the subarray to the right. As we expand the subarray, we can efficiently update the GCD of the current subarray by calculating the GCD of the previous subarray's GCD and the new element.
Algorithm
- Initialize a counter
countto 0. - Iterate through the array with a variable
ifrom 0 ton-1, representing the starting index of a subarray. - For each
i, start a nested loop with a variablejfromiton-1, representing the ending index of the subarray. - Inside the inner loop, maintain a variable
currentGcdfor the subarraynums[i...j]. - In the first iteration of the inner loop (when
j == i), initializecurrentGcdwithnums[j]. - For subsequent iterations (
j > i), updatecurrentGcdby calculatinggcd(currentGcd, nums[j]). - After updating
currentGcd, check if it is equal tok. If it is, increment thecount. - Optimization: If at any point
nums[j]is not divisible byk, we can break the inner loop. This is because for the GCD of a set of numbers to bek, every number in the set must be divisible byk. - After the loops complete, return the total
count.
Walkthrough
This method iterates through every possible starting point i of a subarray. For each starting point, it iterates from i to the end of the array, considering each element nums[j] as the end of the current subarray.
A variable currentGcd is used to keep track of the GCD of the elements in the subarray nums[i...j]. It's initialized with nums[i] and then updated with gcd(currentGcd, nums[j]) as j increases. If at any point currentGcd equals k, we've found a valid subarray and increment our counter.
An important optimization can be made: if we encounter an element nums[j] that is not divisible by k, we can stop extending the subarray from the current start i. This is because any subarray containing an element not divisible by k cannot have k as its GCD. This optimization helps prune the search space.
class Solution { public int subarrayGCD(int[] nums, int k) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { int currentGcd = 0; for (int j = i; j < n; j++) { // Optimization: If an element is not divisible by k, // no subarray including it can have a GCD of k. if (nums[j] % k != 0) { break; } if (j == i) { currentGcd = nums[j]; } else { currentGcd = gcd(currentGcd, nums[j]); } if (currentGcd == k) { count++; } } } return count; } // Helper function to calculate GCD using Euclidean algorithm private int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; }}Complexity
Time
O(N^2 * log(M)), where N is the number of elements in `nums` and M is the maximum possible value of an element. The two nested loops give a factor of N^2, and the GCD calculation takes logarithmic time.
Space
O(1), as we only use a few variables to store the count and the current GCD.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space.
Cons
The time complexity of O(N^2 * log(M)) might be too slow for larger constraints, although it passes for N=1000.
Solutions
Solution
class Solution {public int subarrayGCD(int[] nums, int k) { int n = nums.length; int ans = 0; for (int i = 0; i < n; ++i) { int g = 0; for (int j = i; j < n; ++j) { g = gcd(g, nums[j]); if (g == k) { ++ans; } } } return ans; }private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.