Number of Subarrays With GCD Equal to K solution and explanation
9 more videos on this problem
2447. Number of Subarrays With GCD Equal to K | Leetcode Weekly 316 | LeetCode 2447Bro Coders · 6:30 · 2K views
Number of Subarrays With GCD Equal to K | leetcode Weekly 316 | Leetcode MediumBinaryMagic · 6:57 · 940 views
2447. Number of Subarrays With GCD Equal to K (Leetcode Medium)Programming Live with Larry · 4:17 · 603 views
Leetcode 2447: Number of Subarrays With GCD Equal to KAlgorithms Casts · 8:26 · 585 views
Leetcode Weekly contest 316 - Medium - Number of Subarrays With GCD Equal to KPrakhar Agrawal · 7:13 · 516 views
Number of Subarrays With GCD Equal to K - Leetcode 2447 - PythonCheatCode Ninja · 4:17 · 348 views
2447 Number of Subarrays With GCD Equal to K | Leetcode Weekly contest 316Ashutosh sharma · 7:46 · 289 views
Number of Subarrays With GCD Equal to K || Weekly Contest 316 || C++Priyanshi Porwal · 3:26 · 284 views
Leetcode 2447 Number of Subarrays With GCD Equal to K | HindiThinkCode · 3:31 · 220 views
2447. Number of Subarrays With GCD Equal to K || Leetcode Contest Medium|| Math || CPPCoding Techniques with Komal | Newton School · 10:00 · 180 views
The problem
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 <= 10001 <= nums[i], k <= 109
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.
from math import gcd
def subarraysWithGCD(nums, k):
count = 0
for i in range(len(nums)):
current_gcd = 0
for j in range(i, len(nums)):
current_gcd = gcd(current_gcd, nums[j])
if current_gcd == k:
count += 1
if current_gcd < k:
break
return count
nums = [9, 3, 1, 2, 6, 3]
k = 3
print(subarraysWithGCD(nums, k))public class Solution {
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public int subarraysWithGCD(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int current_gcd = 0;
for (int j = i; j < nums.length; j++) {
current_gcd = gcd(current_gcd, nums[j]);
if (current_gcd == k) {
count++;
}
if (current_gcd < k) {
break;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {9, 3, 1, 2, 6, 3};
int k = 3;
System.out.println(sol.subarraysWithGCD(nums, k));
}
}#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
int subarraysWithGCD(vector<int>& nums, int k) {
int n = nums.size(), res = 0;
for (int i = 0; i < n; ++i) {
int current_gcd = 0;
for (int j = i; j < n; ++j) {
current_gcd = gcd(current_gcd, nums[j]);
if (current_gcd == k) {
++res;
}
if (current_gcd < k) {
break;
}
}
}
return res;
}
int main() {
vector<int> nums = {9, 3, 1, 2, 6, 3};
int k = 3;
cout << subarraysWithGCD(nums, k) << endl;
return 0;
}function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
function subarraysWithGCD(nums, k) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let currentGCD = 0;
for (let j = i; j < nums.length; j++) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD === k) {
count++;
}
if (currentGCD < k) {
break;
}
}
}
return count;
}
let nums = [9, 3, 1, 2, 6, 3];
let k = 3;
console.log(subarraysWithGCD(nums, k));#include <stdio.h>
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
int subarraysWithGCD(int* nums, int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
int current_gcd = 0;
for (int j = i; j < numsSize; j++) {
current_gcd = gcd(current_gcd, nums[j]);
if (current_gcd == k) {
count++;
}
if (current_gcd < k) {
break;
}
}
}
return count;
}
int main() {
int nums[] = {9, 3, 1, 2, 6, 3};
int k = 3;
int result = subarraysWithGCD(nums, sizeof(nums) / sizeof(nums[0]), k);
printf("%d\n", result);
return 0;
}using System;
class Solution {
public int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
public int SubarraysWithGCD(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
int current_gcd = 0;
for (int j = i; j < nums.Length; j++) {
current_gcd = GCD(current_gcd, nums[j]);
if (current_gcd == k) {
count++;
}
if (current_gcd < k) {
break;
}
}
}
return count;
}
static void Main() {
Solution sol = new Solution();
int[] nums = {9, 3, 1, 2, 6, 3};
int k = 3;
Console.WriteLine(sol.SubarraysWithGCD(nums, k));
}
}The Python solution uses the gcd function from the math module to simplify the calculation of GCD, iterating over subarrays and increasing the count when the GCD matches k.
Time Complexity: O(n^2)
Space Complexity: O(1)
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.
from math import gcd
def subarraysWithGCD(nums, k):
count = 0
for i in range(len(nums)):
if nums[i] % k != 0: continue
current_gcd = nums[i]
for j in range(i, len(nums)):
current_gcd = gcd(current_gcd, nums[j])
if current_gcd == k:
count += 1
if current_gcd < k:
break
return count
nums = [9, 3, 1, 2, 6, 3]
k = 3
print(subarraysWithGCD(nums, k))public class Solution {
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public int subarraysWithGCD(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] % k != 0) continue;
int current_gcd = nums[i];
for (int j = i; j < nums.length; j++) {
current_gcd = gcd(current_gcd, nums[j]);
if (current_gcd == k) {
count++;
}
if (current_gcd < k) {
break;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {9, 3, 1, 2, 6, 3};
int k = 3;
System.out.println(sol.subarraysWithGCD(nums, k));
}
}#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
int subarraysWithGCD(vector<int>& nums, int k) {
int n = nums.size(), res = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] % k != 0) continue;
int current_gcd = nums[i];
for (int j = i; j < n; ++j) {
current_gcd = gcd(current_gcd, nums[j]);
if (current_gcd == k) {
++res;
}
if (current_gcd < k) {
break;
}
}
}
return res;
}
int main() {
vector<int> nums = {9, 3, 1, 2, 6, 3};
int k = 3;
cout << subarraysWithGCD(nums, k) << endl;
return 0;
}function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
function subarraysWithGCD(nums, k) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] % k !== 0) continue;
let currentGCD = nums[i];
for (let j = i; j < nums.length; j++) {
currentGCD = gcd(currentGCD, nums[j]);
if (currentGCD === k) {
count++;
}
if (currentGCD < k) {
break;
}
}
}
return count;
}
let nums = [9, 3, 1, 2, 6, 3];
let k = 3;
console.log(subarraysWithGCD(nums, k));#include <stdio.h>
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
int subarraysWithGCD(int* nums, int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] % k != 0) continue;
int current_gcd = nums[i];
for (int j = i; j < numsSize; j++) {
current_gcd = gcd(current_gcd, nums[j]);
if (current_gcd == k) {
count++;
}
if (current_gcd < k) {
break;
}
}
}
return count;
}
int main() {
int nums[] = {9, 3, 1, 2, 6, 3};
int k = 3;
int result = subarraysWithGCD(nums, sizeof(nums) / sizeof(nums[0]), k);
printf("%d
", result);
return 0;
}using System;
class Solution {
public int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
public int SubarraysWithGCD(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
if (nums[i] % k != 0) continue;
int current_gcd = nums[i];
for (int j = i; j < nums.Length; j++) {
current_gcd = GCD(current_gcd, nums[j]);
if (current_gcd == k) {
count++;
}
if (current_gcd < k) {
break;
}
}
}
return count;
}
static void Main() {
Solution sol = new Solution();
int[] nums = {9, 3, 1, 2, 6, 3};
int k = 3;
Console.WriteLine(sol.SubarraysWithGCD(nums, k));
}
}The Python code optimizes performance by beginning checks only when the initial element of a subarray is divisible by k, reducing needless calculations and improving efficiency.
Time Complexity: O(n^2), with faster execution due to earlier exits
Space Complexity: O(1)
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.
function subarrayGCD(nums: number[], k: number): number {
let ans = 0;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let g = 0;
for (let j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g === k) {
++ans;
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func subarrayGCD(nums []int, k int) (ans int) {
for i := range nums {
g := 0
for _, x := range nums[i:] {
g = gcd(g, x)
if g == k {
ans++
}
}
}
return
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using GCD Properties | Time Complexity: O(n^2), with faster execution due to earlier exits |
| Direct Enumeration | – |
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. |
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.