LeetCode Problem 2447

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

LeetCode 2447 - Number of Subarrays With GCD Equal to K

Problem Understanding

The problem gives us an integer array nums and an integer k. We need to count how many contiguous subarrays have a greatest common divisor (GCD) exactly equal to k.

A subarray is any non-empty contiguous segment of the array. For every possible subarray, we compute the GCD of all elements inside it. If that GCD equals k, we count it.

For example, if a subarray contains values whose common divisor is exactly k, and no larger integer divides all of them, then that subarray contributes to the answer.

The constraints are important:

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 10^9

The array length is relatively small, only up to 1000. This suggests that an O(n²) solution may be acceptable, while O(n³) would likely be too slow.

The values themselves can be very large, up to 10^9, which means we cannot rely on frequency arrays or value-based preprocessing. Instead, we should leverage mathematical properties of the GCD operation.

Several edge cases are worth considering:

• Arrays containing elements that are not divisible by k.
• Arrays where every element equals k.
• Single-element arrays.
• Cases where no valid subarray exists.
• Cases where the GCD quickly drops below k, allowing early termination.

Approaches

Brute Force

The most direct approach is to enumerate every possible subarray.

For each starting index, we generate every ending index and compute the GCD of all elements inside that subarray from scratch. If the resulting GCD equals k, we increment the answer.

This approach is correct because it explicitly checks every possible subarray. However, computing the GCD of each subarray independently is expensive.

There are O(n²) subarrays, and computing the GCD of a subarray may require up to O(n) work. Therefore the total complexity becomes O(n³).

With n = 1000, this would require roughly one billion operations in the worst case, which is far too slow.

Key Insight

The key observation is that GCD has an incremental property:

$$\gcd(a,b,c)=\gcd(\gcd(a,b),c)$$

When extending a subarray by one element, we do not need to recompute the entire GCD. We can update the current GCD using only the previous GCD and the new element.

For every starting position:

• Initialize the current GCD as 0.
• Extend the subarray one element at a time.
• Update the running GCD.

Another important observation is that GCD values can only decrease or stay the same as more elements are added.

If the current GCD becomes smaller than k, it can never increase again. Therefore, no longer subarray starting from the same position can ever have GCD equal to k.

This allows an early break, significantly reducing unnecessary work.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Recomputes GCD for every subarray independently
Optimal	O(n² log M)	O(1)	Maintains running GCD while extending subarrays

Here, M denotes the maximum value in the array.

Algorithm Walkthrough

Optimal Algorithm

1. Initialize answer = 0.
2. Iterate through every possible starting index left.
3. For each starting index, initialize current_gcd = 0.
4. Extend the subarray by moving the ending index right from left to the end of the array.
5. Update the running GCD:

$$current_gcd = \gcd(current_gcd,\ nums[right])$$

Using 0 initially works because:

$$\gcd(0,x)=x$$ 6. If current_gcd == k, increment the answer because the current subarray satisfies the requirement. 7. If current_gcd < k, stop extending this starting position and move to the next one. Since GCD never increases when more elements are added, reaching a value below k means it can never become k again. 8. After all starting positions have been processed, return the answer.

Why it works

For a fixed starting index, the algorithm examines every possible ending index exactly once and maintains the exact GCD of that subarray using the associative property of GCD. Since every subarray is considered, every valid subarray is counted.

The early termination is valid because GCD values form a non-increasing sequence as elements are added. Once the GCD drops below k, it can never return to k, so no future extension can produce a valid subarray.

Python Solution

from typing import List
from math import gcd

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        answer = 0
        n = len(nums)

        for left in range(n):
            current_gcd = 0

            for right in range(left, n):
                current_gcd = gcd(current_gcd, nums[right])

                if current_gcd == k:
                    answer += 1
                elif current_gcd < k:
                    break

        return answer

The implementation follows the algorithm directly.

The outer loop chooses every possible starting position. For each starting position, the inner loop extends the subarray one element at a time.

The variable current_gcd stores the GCD of the current subarray. Instead of recomputing the GCD from scratch, we update it incrementally using Python's built-in gcd function.

Whenever the running GCD becomes exactly k, we count the subarray. When it falls below k, we immediately stop processing that starting position because no further extension can restore the GCD to k.

This achieves the desired O(n² log M) complexity while using only constant extra space.

Go Solution

func subarrayGCD(nums []int, k int) int {
	ans := 0
	n := len(nums)

	for left := 0; left < n; left++ {
		currentGCD := 0

		for right := left; right < n; right++ {
			currentGCD = gcd(currentGCD, nums[right])

			if currentGCD == k {
				ans++
			} else if currentGCD < k {
				break
			}
		}
	}

	return ans
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

The Go implementation is almost identical to the Python version.

Go does not provide a built-in integer GCD function in the standard library for this use case, so we implement the Euclidean algorithm manually.

No special handling for nil slices is necessary because the problem guarantees at least one element. Integer overflow is not a concern because GCD computations never exceed the original input values.

Worked Examples

Example 1

Input

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

Valid subarrays are:

[9,3]
[3]
[3,1,2,6]
[3,1,2,6,3]

Answer = 4

Trace

left	right	current_gcd	Count Added
0	0	9	No
0	1	3	Yes
0	2	1	Break
1	1	3	Yes
1	2	1	Break
2	2	1	Break
3	3	2	Break
4	4	6	No
4	5	3	Yes
5	5	3	Yes

Total count = 4.

Example 2

Input

nums = [4]
k = 7

Trace

left	right	current_gcd	Count Added
0	0	4	Break

Since the GCD is already less than k, no valid subarray exists.

Answer = 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² log M)	Each subarray extension performs one GCD computation
Space	O(1)	Only a few variables are maintained

The outer loop runs n times and the inner loop can run up to n times, producing O(n²) iterations. Each iteration performs a GCD operation, whose complexity is O(log M) using the Euclidean algorithm. Therefore the total complexity is O(n² log M).

The algorithm uses only a constant number of extra variables, so the auxiliary space complexity is O(1).

Test Cases

from typing import List

s = Solution()

assert s.subarrayGCD([9, 3, 1, 2, 6, 3], 3) == 4  # official example
assert s.subarrayGCD([4], 7) == 0  # official example

assert s.subarrayGCD([3], 3) == 1  # single valid element
assert s.subarrayGCD([5], 3) == 0  # single invalid element

assert s.subarrayGCD([3, 3, 3], 3) == 6  # all subarrays valid
assert s.subarrayGCD([2, 4, 6], 1) == 0  # gcd never reaches k

assert s.subarrayGCD([6, 9, 12], 3) == 4  # multiple overlapping answers
assert s.subarrayGCD([5, 10, 15], 5) == 6  # every subarray valid

assert s.subarrayGCD([8, 16, 32], 4) == 0  # gcd always greater than k
assert s.subarrayGCD([7, 14, 21], 7) == 6  # all subarrays gcd 7

assert s.subarrayGCD([2, 3, 5, 7], 1) == 6  # gcd eventually becomes 1
assert s.subarrayGCD([1000000000], 1000000000) == 1  # maximum value

Test Summary

Test	Why
[9,3,1,2,6,3], k=3	Official example
[4], k=7	No valid subarray
[3], k=3	Single-element success
[5], k=3	Single-element failure
[3,3,3], k=3	Every subarray valid
[2,4,6], k=1	GCD never reaches target
[6,9,12], k=3	Mixed valid and invalid ranges
[5,10,15], k=5	Every subarray shares same GCD
[8,16,32], k=4	GCD always larger than target
[7,14,21], k=7	Multiple valid subarrays
[2,3,5,7], k=1	GCD gradually decreases to 1
[1000000000], k=1000000000	Maximum value boundary

Edge Cases

Single-Element Arrays

When the array contains only one element, the answer depends entirely on whether that element equals k. A buggy implementation may accidentally assume every valid subarray has length at least two. The presented solution naturally handles this because every element forms a subarray by itself.

GCD Drops Below K Early

Consider nums = [9, 3, 1] and k = 3. After processing the third element, the GCD becomes 1. Since GCD values can only decrease, there is no reason to continue extending the subarray. The implementation correctly breaks out of the inner loop, improving efficiency without missing any valid answers.

Elements Not Divisible by K

Consider nums = [4] and k = 7. The GCD immediately becomes 4, which is already smaller than 7. No future extension could increase the GCD to 7. The algorithm correctly terminates early and returns zero.

All Elements Equal K

For nums = [k, k, k], every possible subarray has GCD equal to k. The implementation counts each one because the running GCD remains exactly k throughout every extension. This verifies that the algorithm handles the maximum number of valid subarrays correctly.

GCD Always Greater Than K

Consider nums = [8, 16, 32] and k = 4. Every subarray has GCD at least 8. The algorithm never increments the answer because the running GCD never becomes exactly 4, which is the required condition.