#2447

Medium

LeetCode Problem Workspace

Number of Subarrays With GCD Equal to K

Count the number of subarrays with GCD equal to a given value k from a list of integers.

Problem Statement

Given an integer array nums and an integer k, you are tasked with returning the number of subarrays of nums where the greatest common divisor (GCD) of the elements of the subarray equals k.

A subarray is defined as a contiguous non-empty sequence of elements within the array. The greatest common divisor of a set of numbers is the largest integer that divides all numbers in the set without leaving a remainder.

Examples

Example 1

Input: nums = [9,3,1,2,6,3], k = 3

Output: 4

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

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 Approach

Brute Force Approach

One simple method is to check each subarray's GCD by iterating over all possible subarrays. For each subarray, calculate the GCD and compare it to k. This solution works but may become inefficient as the size of nums increases due to the number of subarrays being quadratic.

Optimized Sliding Window Approach

Another approach is to use a sliding window to traverse the array. As we slide, we can progressively calculate the GCD of the elements within the window. If at any point the GCD equals k, we count that subarray.

Mathematical Insights

Understanding the mathematical properties of GCD can help optimize the approach. For example, if the GCD of a set of numbers is k, then any subarray containing numbers with GCD greater than k can be skipped, reducing unnecessary calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force method has a time complexity of O(n^2 * log(m)), where n is the length of the array and m is the largest number in the array. The sliding window method can reduce the time complexity by focusing on fewer subarrays, but still, the time complexity may depend on the efficiency of the GCD calculation.

What Interviewers Usually Probe

Candidate identifies that brute-force approach may not scale well and proposes optimizations.
Candidate suggests using sliding window technique for efficiency, ensuring correctness with GCD checks.
Candidate mentions mathematical insights into GCD that could simplify the problem or reduce unnecessary work.

Common Pitfalls or Variants

Common pitfalls

Overlooking the need to calculate GCD for every subarray, leading to inefficiency.
Failure to recognize when GCD exceeds k, causing unnecessary subarray checks.
Confusing the greatest common divisor calculation with other operations, leading to incorrect results.

Follow-up variants

What if the array contains repeated elements? How does this affect GCD calculations?
How would the problem change if we had to check subarrays with GCD greater than k instead?
Consider handling edge cases like a single element array or when k is greater than any element.

FAQ

What is the primary approach to solving the "Number of Subarrays With GCD Equal to K" problem?

The primary approach involves checking subarrays for their GCD and comparing it to the given value k, with optimizations such as the sliding window technique.

How can I optimize the brute-force solution for the Number of Subarrays With GCD Equal to K?

One way to optimize the brute-force approach is by using a sliding window to dynamically calculate the GCD as you iterate through the array, reducing redundant calculations.

What are common mistakes when solving the "Number of Subarrays With GCD Equal to K" problem?

Common mistakes include inefficient brute-force solutions, skipping edge cases, and misunderstanding how to calculate the GCD of subarrays correctly.

How does the sliding window technique work in the Number of Subarrays With GCD Equal to K?

The sliding window technique works by progressively calculating the GCD for elements within the window, moving the window across the array and checking if the GCD equals k.

How can mathematical properties of GCD be applied to optimize solving this problem?

Mathematical properties, such as recognizing when GCD exceeds k or leveraging known divisibility rules, can reduce unnecessary subarray checks and speed up the process.

terminal

Solution

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

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2470 number of subarrays with lcm equal to k #2521 distinct prime factors of product of array #2344 minimum deletions to make array divisible