Number of Subarrays With GCD Equal to K — Problem & Solution
Number of Subarrays With GCD Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Subarrays With GCD Equal to K is a medium coding problem on arrays, math and number theory, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer k, return the number of subarrays (contiguous, non-empty) whose elements have a greatest common divisor equal to k.
The greatest common divisor of a set of numbers is the largest integer that divides every one of them.
Example 1
Input: nums = [6,3,12,9,2], k = 3
Output: 7
Explanation: `[6,3]`, `[6,3,12]`, `[6,3,12,9]`, `[3]`, `[3,12]`, `[3,12,9]` and `[12,9]`.
Example 2
Input: nums = [5], k = 2
Output: 0
Example 3
Input: nums = [4,4,4], k = 4
Output: 6
Explanation: Every one of the six subarrays has GCD 4.
Constraints
1 <= nums.length <= 10001 <= nums[i], k <= 10^9
Hints for Number of Subarrays With GCD Equal to K
Hint 1
Fix the left end and extend the right end one element at a time — the GCD can be updated incrementally.
Hint 2
As a subarray grows, its GCD only stays the same or drops to a divisor of itself.
Hint 3
Once the running GCD is no longer a multiple of
k, no extension can bring it back tok: stop extending.
How to solve Number of Subarrays With GCD Equal to K
For a fixed start, the GCD of nums[i..j] is gcd(GCD of nums[i..j-1], nums[j]), so all subarrays with that start cost one gcd step each. And once that GCD stops being a multiple of k, it never will be again.
Approach
- For each start
i, setg = 0(gcd(0, x) = x). - For
j = i..n-1, updateg = gcd(g, nums[j]). - If
g % k != 0, break — every longer subarray also fails. - If
g == k, count the subarray.
Why it works
The running GCD of a growing subarray divides the previous one. If k does not divide it, k does not divide any later value either (they are divisors of it), so none of them can equal k. Every subarray is otherwise visited once, so the count is exact.
Complexity
- Time —
O(n^2 log(max)) - Space —
O(1)
Pitfalls
- Start the running GCD at 0 (or at
nums[i]), not at 1 — gcd(1, x) is always 1. - Breaking when
g < kalone is not enough; break whenkdoes not divideg. - A single element equal to
kis a valid subarray.
Reference solution
Python
from typing import List
from math import gcd
def subarrayGCD(nums: List[int], k: int) -> int:
n = len(nums)
count = 0
for i in range(n):
g = 0
for j in range(i, n):
g = gcd(g, nums[j])
if g % k != 0:
break
if g == k:
count += 1
return countJava
static int gcdSub(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
public static int subarrayGCD(int[] nums, int k) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
int g = 0;
for (int j = i; j < n; j++) {
g = gcdSub(g, nums[j]);
if (g % k != 0) break;
if (g == k) count++;
}
}
return count;
}C++
static int gcdSub(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
int subarrayGCD(vector<int>& nums, int k) {
int n = nums.size(), count = 0;
for (int i = 0; i < n; i++) {
int g = 0;
for (int j = i; j < n; j++) {
g = gcdSub(g, nums[j]);
if (g % k != 0) break;
if (g == k) count++;
}
}
return count;
}JavaScript
var subarrayGCD = function(nums, k) {
var gcd = function(a, b) {
while (b !== 0) { var t = a % b; a = b; b = t; }
return a;
};
var n = nums.length, count = 0;
for (var i = 0; i < n; i++) {
var g = 0;
for (var j = i; j < n; j++) {
g = gcd(g, nums[j]);
if (g % k !== 0) break;
if (g === k) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays