Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

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

All Problems

All Solutions