Problem Description

You are given an integer array nums and an integer k. Your task is to find and count how many subarrays have a greatest common divisor (GCD) equal to k.

A subarray is a contiguous sequence of elements from the array. For example, if nums = [1, 2, 3], then [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3] are all possible subarrays.

The greatest common divisor (GCD) of an array is the largest positive integer that divides all elements in that array evenly. For instance, the GCD of [6, 12, 18] is 6 because 6 is the largest number that divides all three numbers without remainder.

The solution works by checking every possible subarray. For each starting position i, it examines all subarrays beginning at that position. It maintains a running GCD value g that gets updated as each new element is included in the subarray. When extending the subarray to include nums[j], the GCD is updated using g = gcd(g, nums[j]). Whenever the current GCD equals k, the counter is incremented by 1.

The algorithm uses the property that the GCD of a set of numbers can be computed incrementally: gcd(a, b, c) = gcd(gcd(a, b), c). This allows efficient calculation of the GCD for each subarray without recomputing from scratch.

Intuition

The key insight is that we need to check every possible subarray to determine if its GCD equals k. Since a subarray is defined by its starting and ending positions, we can systematically examine all possibilities.

The brute force approach naturally emerges when we think about how to generate all subarrays: pick a starting point, then extend the subarray one element at a time to the right. For each extension, we check if the GCD of the current subarray equals k.

The clever part is recognizing that we don't need to recalculate the GCD from scratch for each subarray. When we extend a subarray by adding one more element, we can update the GCD incrementally. This works because of the mathematical property: gcd(a, b, c) = gcd(gcd(a, b), c).

Starting with g = 0 is another smart trick. Since gcd(0, x) = x for any positive integer x, initializing g = 0 means that after processing the first element, g will equal that element. This eliminates the need for special handling of the first element.

As we extend each subarray, the GCD can only stay the same or decrease (it can never increase when adding more numbers). This property means that once the GCD drops below k, we might still find subarrays with GCD equal to k by continuing to add elements, but only if those elements are multiples of k.

The nested loop structure naturally captures this process: the outer loop fixes the starting position, while the inner loop extends the subarray element by element, updating the GCD and counting matches along the way.

Learn more about Math patterns.

Solution Approach

The solution uses a direct enumeration approach with nested loops to examine all possible subarrays.

Algorithm Steps:

1. Initialize a counter ans = 0 to track the number of subarrays with GCD equal to k.

2. Use the outer loop to iterate through each possible starting position i from 0 to len(nums) - 1.

3. For each starting position i, initialize g = 0 to track the GCD of the current subarray. Setting g = 0 initially is a trick since gcd(0, x) = x for any positive integer x.

4. Use an inner loop to iterate through elements from position i to the end of the array. This loop extends the subarray one element at a time by including nums[j] where j goes from i to len(nums) - 1.

5. For each new element x in the inner loop:

   • Update the GCD: g = gcd(g, x)
   • Check if the current GCD equals k: if g == k, increment the answer by 1

6. After both loops complete, return ans.

Key Implementation Details:

• The code uses Python's built-in gcd function from the math module to compute the greatest common divisor.
• The expression nums[i:] creates a slice starting from index i to the end, which the inner loop iterates through.
• The line ans += g == k is a Pythonic way of incrementing the counter when the condition is true (since True equals 1 in Python).

Time Complexity: O(n² × log(max(nums))) where n is the length of the array. The nested loops give O(n²), and each GCD computation takes O(log(max(nums))) time.

Space Complexity: O(1) as we only use a constant amount of extra space for variables ans and g.

Example Walkthrough

Let's walk through the solution with nums = [6, 3, 12, 9] and k = 3.

We'll examine all possible subarrays and track their GCDs:

Starting at index 0 (element 6):

• Initialize g = 0
• Subarray [6]: g = gcd(0, 6) = 6. Since 6 ≠ 3, don't count it.
• Subarray [6, 3]: g = gcd(6, 3) = 3. Since 3 = 3, increment counter to 1.
• Subarray [6, 3, 12]: g = gcd(3, 12) = 3. Since 3 = 3, increment counter to 2.
• Subarray [6, 3, 12, 9]: g = gcd(3, 9) = 3. Since 3 = 3, increment counter to 3.

Starting at index 1 (element 3):

• Initialize g = 0
• Subarray [3]: g = gcd(0, 3) = 3. Since 3 = 3, increment counter to 4.
• Subarray [3, 12]: g = gcd(3, 12) = 3. Since 3 = 3, increment counter to 5.
• Subarray [3, 12, 9]: g = gcd(3, 9) = 3. Since 3 = 3, increment counter to 6.

Starting at index 2 (element 12):

• Initialize g = 0
• Subarray [12]: g = gcd(0, 12) = 12. Since 12 ≠ 3, don't count it.
• Subarray [12, 9]: g = gcd(12, 9) = 3. Since 3 = 3, increment counter to 7.

Starting at index 3 (element 9):

• Initialize g = 0
• Subarray [9]: g = gcd(0, 9) = 9. Since 9 ≠ 3, don't count it.

Final answer: 7 subarrays have GCD equal to 3

The subarrays with GCD = 3 are: [6,3], [6,3,12], [6,3,12,9], [3], [3,12], [3,12,9], and [12,9].

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × (n + log M)), where n is the length of the array nums and M is the maximum value in the array.

The analysis breaks down as follows:

• The outer loop runs n times (iterating through each starting position i)
• For each starting position i, the inner loop iterates through all elements from position i to the end, which takes O(n) iterations in the worst case
• Within each inner loop iteration, we compute gcd(g, x), which takes O(log M) time where M is the maximum value being processed
• The total number of GCD computations is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)
• Therefore, the total time complexity is O(n² × log M) = O(n × n × log M) = O(n × (n + log M)) when simplified according to the reference answer's notation

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variable ans to store the count
• Variable g to store the running GCD
• Loop variables i and x

All these variables use constant space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Early Termination Optimization Gone Wrong

A common mistake is attempting to optimize by breaking the inner loop when the GCD becomes less than k, thinking that adding more elements can't increase the GCD back to k.

Incorrect Implementation:

for start_idx in range(len(nums)):
    current_gcd = 0
    for num in nums[start_idx:]:
        current_gcd = gcd(current_gcd, num)
        if current_gcd < k:
            break  # WRONG: This causes early termination
        if current_gcd == k:
            count += 1

Why This Is Wrong: The GCD can only decrease or stay the same as we add more elements—it never increases. However, the GCD might start higher than k and later become equal to k. Breaking when current_gcd < k would miss valid subarrays.

Example:

• nums = [12, 6, 3], k = 3
• Subarray [12] has GCD = 12
• Subarray [12, 6] has GCD = 6
• Subarray [12, 6, 3] has GCD = 3 (equals k!)

If we broke when GCD < k, we'd never find the valid subarray [12, 6, 3].

Correct Optimization: Only break when the GCD becomes less than k AND k doesn't divide the current GCD:

for start_idx in range(len(nums)):
    current_gcd = 0
    for num in nums[start_idx:]:
        current_gcd = gcd(current_gcd, num)
        if current_gcd == k:
            count += 1
        elif current_gcd % k != 0:
            break  # Safe to break: GCD can't become k anymore

Pitfall 2: Misunderstanding GCD Calculation with Zero

Incorrect Assumption:

# Some might initialize with the first element
current_gcd = nums[start_idx]  
for num in nums[start_idx + 1:]:  # Skip first element
    current_gcd = gcd(current_gcd, num)

Why the Original Is Better: Starting with current_gcd = 0 and iterating through all elements (including the first) is cleaner because gcd(0, x) = x. This eliminates special case handling and makes the code more elegant.

Pitfall 3: Not Handling Edge Cases

Missing Validation:

def subarrayGCD(self, nums: List[int], k: int) -> int:
    # Should validate that k can be a valid GCD
    count = 0
    # ... rest of the code

Better Implementation with Validation:

def subarrayGCD(self, nums: List[int], k: int) -> int:
    # Early return if k cannot be a valid GCD
    if not any(num % k == 0 for num in nums):
        return 0
  
    count = 0
    for start_idx in range(len(nums)):
        current_gcd = 0
        for num in nums[start_idx:]:
            # Skip elements not divisible by k (optimization)
            if num % k != 0:
                break
            current_gcd = gcd(current_gcd, num)
            if current_gcd == k:
                count += 1
              
    return count

This optimization checks if any element is divisible by k first, and breaks the inner loop early when encountering an element not divisible by k, since the GCD can never be k if any element in the subarray isn't divisible by k.