Number of Subarrays With GCD Equal to K

Medium
1163.

Number of Subarrays With GCD Equal to K

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.

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 <= 1000
  • 1 <= nums[i], k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarrayGCD = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 1 <= nums[i], k <= 10^9

Hints for Number of Subarrays With GCD Equal to K

  1. Hint 1

    Fix the left end and extend the right end one element at a time — the GCD can be updated incrementally.

  2. Hint 2

    As a subarray grows, its GCD only stays the same or drops to a divisor of itself.

  3. Hint 3

    Once the running GCD is no longer a multiple of k, no extension can bring it back to k: 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

  1. For each start i, set g = 0 (gcd(0, x) = x).
  2. For j = i..n-1, update g = gcd(g, nums[j]).
  3. If g % k != 0, break — every longer subarray also fails.
  4. 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 < k alone is not enough; break when k does not divide g.
  • A single element equal to k is 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 count

Java

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