# Number of Subarrays With GCD Equal to K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/number-of-subarrays-with-gcd-equal-to-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
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 <= 109`

# Approaches
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimized Approach using GCD Properties
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`.
**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.
**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.
### Explanation
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.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int ans = 0;
        // Map from gcd_value -> count of subarrays ending at current position with this gcd
        Map<Integer, Integer> gcds = new HashMap<>();

        for (int num : nums) {
            Map<Integer, Integer> newGcds = new HashMap<>();
            if (num % k == 0) {
                // Start a new subarray with just the current number
                newGcds.put(num, 1);

                // Extend previous subarrays
                for (Map.Entry<Integer, Integer> entry : gcds.entrySet()) {
                    int prevGcd = entry.getKey();
                    int count = entry.getValue();
                    int newGcd = gcd(prevGcd, num);
                    newGcds.put(newGcd, newGcds.getOrDefault(newGcd, 0) + count);
                }

                // Add to the answer if we found subarrays with GCD equal to k
                if (newGcds.containsKey(k)) {
                    ans += newGcds.get(k);
                }
            }
            // The new map becomes the map for the next iteration.
            // If num % k != 0, this will be an empty map, effectively resetting.
            gcds = newGcds;
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### 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.

# Solutions
### Java

```java
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); }
}

```

### CPP

```cpp
class Solution {
public:
  int subarrayGCD(vector<int> &nums, int k) {
    int n = nums.size();
    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]);
        ans += g == k;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```