##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2447.html

# 2447. Number of Subarrays With GCD Equal to K

• Difficulty: Medium.
• Related Topics: Array, Math, Number Theory.
• Similar Questions: Find Greatest Common Divisor of 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

## Solution (Java, C++, Python)

• class Solution {
public int subarrayGCD(int[] nums, int k) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int x = nums[i];
for (int j = i; j < n; ++j) {
x = gcd(x, nums[j]);
if (x == 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 x = nums[i];
for (int j = i; j < n; ++j) {
x = __gcd(x, nums[j]);
ans += x == k;
}
}
return ans;
}
};

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


• func subarrayGCD(nums []int, k int) int {
ans, n := 0, len(nums)
for i, x := range nums {
for j := i; j < n; j++ {
x = gcd(x, nums[j])
if x == k {
ans++
}
}
}
return ans
}

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

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

function gcd(a: number, b: number): number {
if (a > b) [a, b] = [b, a];
if (a == 0) return b;
return gcd(b % a, a);
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).