Number of Subarrays With GCD Equal to K - Solution & Explanation

Q: Is Number of Subarrays With GCD Equal to K easy or hard?

The problem is rated Medium because the brute force solution is straightforward but inefficient. Recognizing that subarrays share intermediate GCD values and compressing those states into a smaller set requires deeper understanding of GCD properties and optimization techniques.

Q: Number of Subarrays With GCD Equal to K Python/Java solution

Both Python and Java implementations rely on the Euclidean algorithm to compute GCD values while iterating through the array. The optimized version stores previous GCD results and updates them for each new element, producing an O(n log V) solution suitable for large inputs.

Q: How to solve Number of Subarrays With GCD Equal to K in O(n)?

A near-linear solution uses incremental GCD tracking. Maintain all distinct GCDs for subarrays ending at the current index and update them when a new element is processed. Because the number of distinct GCD values remains small, the effective complexity becomes O(n log V), which is close to linear in practice.

Q: What is the best approach for Number of Subarrays With GCD Equal to K?

The most efficient approach maintains distinct GCD values for subarrays ending at each index and compresses identical results. Instead of recalculating every subarray independently, it reuses previously computed GCDs and updates them with the current element. This reduces the complexity to about O(n log V), where V is the maximum array value.

Q: Is Number of Subarrays With GCD Equal to K asked at Google/Amazon/Meta?

GCD-based subarray problems frequently appear in interviews at companies like Google, Amazon, and other large tech firms because they test number theory fundamentals and array optimization techniques. Variations involving subarray GCD, LCM, or divisibility are common in coding rounds.

Q: What data structure is used in Number of Subarrays With GCD Equal to K?

The optimized solution typically uses a map or list of pairs to store distinct GCD values and their frequencies for subarrays ending at the current index. This structure allows quick updates when computing new GCDs with the incoming element.

Q: What is the time complexity of Number of Subarrays With GCD Equal to K?

The brute force approach runs in O(n^2 log V) because every subarray is explored and each extension requires a GCD computation. The optimized approach reduces this to roughly O(n log V) by tracking only distinct GCD values for subarrays ending at each position.

MediumArray Math Number Theory17 min read

Practice this problem

Problem Statement

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 <= 10⁹

Approach Overview

Problem Overview: Given an integer array nums and an integer k, count how many contiguous subarrays have a greatest common divisor (GCD) exactly equal to k. The challenge is that every subarray has its own GCD, so a naive enumeration quickly becomes expensive for larger arrays.

Approach 1: Brute Force with Incremental GCD (O(n² log M) time, O(1) space)

Iterate over every possible starting index and extend the subarray one element at a time. Maintain a running gcd value using the current element and the previous GCD. Each time you extend the subarray, compute gcd(currentGCD, nums[j]). If the result equals k, increment the count. If the GCD drops below k or becomes a value that cannot reach k, you can stop extending that subarray. The main work comes from repeatedly computing GCD values, which costs O(log M) where M is the maximum number in the array. This approach directly demonstrates how GCD evolves as a subarray grows.

This method relies heavily on properties of the Euclidean algorithm from number theory. While simple to implement, the nested loops make it quadratic in the worst case, which may be borderline for large inputs.

Approach 2: Optimized Using GCD Compression (O(n log M) time, O(log M) space)

A key observation: the number of distinct GCD values for subarrays ending at a fixed index is small. Instead of recomputing every subarray independently, maintain a collection of pairs representing (gcd value, frequency) for all subarrays ending at the previous index. For the current element, compute new GCDs by combining nums[i] with each previous GCD and merging identical results.

This effectively compresses multiple subarrays that share the same GCD into one entry. Each step produces only a limited set of distinct GCDs, so the total work stays around O(n log M). Whenever a computed GCD equals k, add its frequency to the answer.

The algorithm processes the array once and repeatedly applies the Euclidean GCD operation, making it a strong mix of array traversal and math reasoning. It avoids exploring every possible subarray explicitly.

Recommended for interviews: Start with the brute force idea to show you understand how subarray GCDs evolve. Then move to the optimized GCD-compression technique. Interviewers typically expect the optimized approach because it demonstrates deeper knowledge of GCD properties and how to reduce repeated work across overlapping subarrays.

Approach 1: Brute Force Approach

This is a straightforward method to solve the problem by calculating the GCD for every possible subarray in the given list and checking if it equals k. Although not the most efficient, it works within the constraints.

The C solution iterates over all possible subarrays and calculates the GCD of elements using a helper function. Whenever the current GCD matches k, it increments the count. We break the inner loop if the current GCD becomes less than k to optimize unnecessary checks.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Optimized Approach Using GCD Properties

This approach leverages properties of GCD to reduce unnecessary calculations. Given that the GCD can only decrease or remain the same when expanding a subarray, the inner loop can stop early when the current GCD drops below k, further enhancing efficiency.

In the C optimized solution, we start by checking if the current number is divisible by k before computing the GCD. This eliminates unnecessary calculations and checks subarrays beginning only with potential contributors to valid GCD.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2), but faster due to early exits
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: 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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n^2) Space Complexity: O(1)
Optimized Approach Using GCD Properties	Time Complexity: O(n^2), but faster due to early exits Space Complexity: O(1)
Direct Enumeration	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force with Incremental GCD	O(n² log M)	O(1)	Good for understanding GCD behavior in subarrays or when input size is small.
Optimized GCD Compression	O(n log M)	O(log M)	Best general solution. Efficient for large arrays by reusing GCD results from previous subarrays.

Video Solution

2447. Number of Subarrays With GCD Equal to K | Leetcode Weekly 316 | LeetCode 2447 • Bro Coders • 2,528 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Subarrays With GCD Equal to K easy or hard?

The problem is rated Medium because the brute force solution is straightforward but inefficient. Recognizing that subarrays share intermediate GCD values and compressing those states into a smaller set requires deeper understanding of GCD properties and optimization techniques.

Number of Subarrays With GCD Equal to K Python/Java solution

Both Python and Java implementations rely on the Euclidean algorithm to compute GCD values while iterating through the array. The optimized version stores previous GCD results and updates them for each new element, producing an O(n log V) solution suitable for large inputs.

How to solve Number of Subarrays With GCD Equal to K in O(n)?

A near-linear solution uses incremental GCD tracking. Maintain all distinct GCDs for subarrays ending at the current index and update them when a new element is processed. Because the number of distinct GCD values remains small, the effective complexity becomes O(n log V), which is close to linear in practice.

What is the best approach for Number of Subarrays With GCD Equal to K?

The most efficient approach maintains distinct GCD values for subarrays ending at each index and compresses identical results. Instead of recalculating every subarray independently, it reuses previously computed GCDs and updates them with the current element. This reduces the complexity to about O(n log V), where V is the maximum array value.

Is Number of Subarrays With GCD Equal to K asked at Google/Amazon/Meta?

GCD-based subarray problems frequently appear in interviews at companies like Google, Amazon, and other large tech firms because they test number theory fundamentals and array optimization techniques. Variations involving subarray GCD, LCM, or divisibility are common in coding rounds.

What data structure is used in Number of Subarrays With GCD Equal to K?

The optimized solution typically uses a map or list of pairs to store distinct GCD values and their frequencies for subarrays ending at the current index. This structure allows quick updates when computing new GCDs with the incoming element.

What is the time complexity of Number of Subarrays With GCD Equal to K?

The brute force approach runs in O(n^2 log V) because every subarray is explored and each extension requires a GCD computation. The optimized approach reduces this to roughly O(n log V) by tracking only distinct GCD values for subarrays ending at each position.

Ready to solve this problem?

Practice Number of Subarrays With GCD Equal to K with our built-in code editor and test cases.

Practice on FleetCode

Find Greatest Common Divisor of Array

Number of Subarrays With LCM Equal to K

Problem Info

DifficultyMedium

Acceptance53.3%

Approaches3

Reading time17 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Brute Force Approach

Code

Complexity

Approach 2: Optimized Approach Using GCD Properties

Code

Complexity

Approach 3: Direct Enumeration

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents