Question

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:
  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

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

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