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).

All Problems

All Solutions