Number of Subarrays With GCD Equal to K

Med

#2231Time: 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.

Patterns

Math Number Theory

Data structures

Array

Prompt

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 <= 1000
1 <= nums[i], k <= 10⁹

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 count to 0.
Iterate through the array with a variable i from 0 to n-1, representing the starting index of a subarray.
For each i, start a nested loop with a variable j from i to n-1, representing the ending index of the subarray.
Inside the inner loop, maintain a variable currentGcd for the subarray nums[i...j].
In the first iteration of the inner loop (when j == i), initialize currentGcd with nums[j].
For subsequent iterations (j > i), update currentGcd by calculating gcd(currentGcd, nums[j]).
After updating currentGcd, check if it is equal to k. If it is, increment the count.
Optimization: If at any point nums[j] is not divisible by k, we can break the inner loop. This is because for the GCD of a set of numbers to be k, every number in the set must be divisible by k.
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.

1class Solution {2    public int subarrayGCD(int[] nums, int k) {3        int count = 0;4        int n = nums.length;5 6        for (int i = 0; i < n; i++) {7            int currentGcd = 0;8            for (int j = i; j < n; j++) {9                // Optimization: If an element is not divisible by k,10                // no subarray including it can have a GCD of k.11                if (nums[j] % k != 0) {12                    break;13                }14 15                if (j == i) {16                    currentGcd = nums[j];17                } else {18                    currentGcd = gcd(currentGcd, nums[j]);19                }20 21                if (currentGcd == k) {22                    count++;23                }24            }25        }26        return count;27    }28 29    // Helper function to calculate GCD using Euclidean algorithm30    private int gcd(int a, int b) {31        while (b != 0) {32            int temp = b;33            b = a % b;34            a = temp;35        }36        return a;37    }38}

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.

A more efficient approach leverages a key property of GCDs. For any fixed ending index i, the number of distinct GCD values for all subarrays ending at i (i.e., gcd(nums[j...i]) for j <= i) is very small. Specifically, the sequence of GCDs gcd(nums[i]), gcd(nums[i-1...i]), gcd(nums[i-2...i]), ... is non-increasing. Each time the GCD value decreases, it is reduced by at least half. This means there are at most O(log(nums[i])) distinct GCD values.

We can iterate through the array and, at each step i, maintain a map of all distinct GCDs of subarrays ending at i along with their frequencies. This map can be efficiently constructed from the map of GCDs ending at i-1.

Algorithm

Initialize a result counter ans to 0.
Initialize a hash map, gcds, to store the GCDs of all subarrays ending at the previous position. The map will store {gcd_value: count}.
Iterate through the input array nums with index i.
For each element num = nums[i], create a new temporary hash map newGcds.
If num is divisible by k:
- Add num to newGcds with a count of 1, representing the subarray [num].
- Iterate through each (g, count) pair in the gcds map from the previous step.
- Calculate newG = gcd(g, num).
- Add count to the value of newG in the newGcds map.
After populating newGcds, check if it contains the key k. If it does, add its corresponding value (newGcds.get(k)) to the total ans.
Replace the old gcds map with newGcds for the next iteration.
If num is not divisible by k, simply reset gcds to an empty map, as no valid subarray can end here.
Return ans after iterating through all numbers.

Walkthrough

We process the array element by element. We use a hash map, let's call it gcds, to keep track of the GCDs of all subarrays ending at the current position. The keys of the map are the GCD values, and the values are the counts of subarrays having that GCD.

As we move from index i-1 to i, we compute a new map newGcds for subarrays ending at i. For each entry (g, count) in the old gcds map (for subarrays ending at i-1), we can extend these count subarrays by including nums[i]. The new GCD for these extended subarrays will be gcd(g, nums[i]). We add count to the entry for this new GCD in our newGcds map. We also need to account for the new subarray that consists of only nums[i], so we add nums[i] to newGcds with a count of 1.

After constructing the newGcds map for the current index i, we look up the count for the key k and add it to our total result. Then, newGcds becomes the gcds map for the next iteration.

If nums[i] is not divisible by k, no subarray ending at i can have a GCD of k, so we can simply reset our map and continue.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int subarrayGCD(int[] nums, int k) {6        int ans = 0;7        // Map from gcd_value -> count of subarrays ending at current position with this gcd8        Map<Integer, Integer> gcds = new HashMap<>();9 10        for (int num : nums) {11            Map<Integer, Integer> newGcds = new HashMap<>();12            if (num % k == 0) {13                // Start a new subarray with just the current number14                newGcds.put(num, 1);15 16                // Extend previous subarrays17                for (Map.Entry<Integer, Integer> entry : gcds.entrySet()) {18                    int prevGcd = entry.getKey();19                    int count = entry.getValue();20                    int newGcd = gcd(prevGcd, num);21                    newGcds.put(newGcd, newGcds.getOrDefault(newGcd, 0) + count);22                }23 24                // Add to the answer if we found subarrays with GCD equal to k25                if (newGcds.containsKey(k)) {26                    ans += newGcds.get(k);27                }28            }29            // The new map becomes the map for the next iteration.30            // If num % k != 0, this will be an empty map, effectively resetting.31            gcds = newGcds;32        }33        return ans;34    }35 36    private int gcd(int a, int b) {37        while (b != 0) {38            int temp = b;39            b = a % b;40            a = temp;41        }42        return a;43    }44}

Complexity

Time

O(N * log(M) * log(M)), where N is the array length and M is the maximum value. For each of the N elements, we iterate through the map of previous GCDs. The size of this map is `O(log M)`, and each step involves a GCD calculation which takes `O(log M)`.

Space

O(log(M)), where M is the maximum value in `nums`. This is because the number of distinct GCDs for subarrays ending at any given index is logarithmically bounded.

Trade-offs

Pros

Significantly faster than the brute-force approach.
Scales well even if N were larger.

Cons

The logic is more complex and less intuitive than the brute-force approach.
Implementation requires careful handling of the hash map.

Solutions

Solution

1class Solution {2public3  int subarrayGCD(int[] nums, int k) {4    int n = nums.length;5    int ans = 0;6    for (int i = 0; i < n; ++i) {7      int g = 0;8      for (int j = i; j < n; ++j) {9        g = gcd(g, nums[j]);10        if (g == k) {11          ++ans;12        }13      }14    }15    return ans;16  }17private18  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }19}

1class Solution {2public:3  int subarrayGCD(vector<int> &nums, int k) {4    int n = nums.size();5    int ans = 0;6    for (int i = 0; i < n; ++i) {7      int g = 0;8      for (int j = i; j < n; ++j) {9        g = gcd(g, nums[j]);10        ans += g == k;11      }12    }13    return ans;14  }15};

1class Solution:2    def subarrayGCD(self, nums: List[int], k: int) -> int: ans = 0 for i in range(len(nums)): g = 0 for x in nums[i:]: g = gcd(g, x) ans += g == k return ans

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.

← Previous

Previous problem

Next problem