# 2447. Number of Subarrays With GCD Equal to K

## Description

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

## Solutions

Solution 1: Direct Enumeration

We can enumerate $nums[i]$ as the left endpoint of the subarray, and then enumerate $nums[j]$ as the right endpoint of the subarray, where $i \le j$. During the enumeration of the right endpoint, we can use a variable $g$ to maintain the greatest common divisor of the current subarray. Each time we enumerate a new right endpoint, we update the greatest common divisor $g = \gcd(g, nums[j])$. If $g=k$, then the greatest common divisor of the current subarray equals $k$, and we increase the answer by $1$.

After the enumeration ends, return the answer.

The time complexity is $O(n \times (n + \log M))$, where $n$ and $M$ are the length of the array $nums$ and the maximum value in the array $nums$, respectively.

• 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);
}
}

• 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;
}
};

• 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


• func subarrayGCD(nums []int, k int) (ans int) {
for i := range nums {
g := 0
for _, x := range nums[i:] {
g = gcd(g, x)
if g == k {
ans++
}
}
}
return
}

func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}

• function subarrayGCD(nums: number[], k: number): number {
let ans = 0;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let g = 0;
for (let j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g === k) {
++ans;
}
}
}
return ans;
}

function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}