LeetCode 2447. Number of Subarrays With GCD Equal to K Solution in Java, C++, Python & More | Explanation + Code

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 × (n + log M)), where n and M are the length of the array nums and the maximum value in the array nums, respectively.

PythonJavaC++GoTypeScript

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(code-box)

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); } }(code-box)

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; } };(code-box)

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) }(code-box)

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); }(code-box)