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.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|