Number of Subarrays With GCD Equal to K - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [9,3,1,2,6,3], k = 3

› Output: 4

💡 Note: The subarrays with GCD = 3 are: [9,3] (GCD=3), [3] at index 1 (GCD=3), [6,3] (GCD=3), [3] at index 5 (GCD=3). Total = 4 subarrays.

Example 2 — Single Element

$ Input: nums = [4], k = 7

› Output: 0

💡 Note: Only one subarray [4] exists, but GCD(4) = 4 ≠ 7, so no valid subarrays.

Example 3 — All Elements Same

$ Input: nums = [6,6,6], k = 6

› Output: 6

💡 Note: All subarrays have GCD = 6: [6], [6], [6], [6,6], [6,6], [6,6,6]. Total = 6 subarrays.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i], k ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that GCD can only decrease or stay same when adding elements to a subarray. The optimized approach uses incremental GCD calculation with early termination when GCD becomes smaller than k. Time: O(n² log(max)), Space: O(1)

Common Approaches

✓ Brute Force - Check All Subarrays

⏱️ Time: O(n³) Space: O(1)

For each starting position, extend the subarray one element at a time and calculate the GCD of all elements in the current subarray. Count how many subarrays have GCD equal to k.

Optimized with Early GCD Calculation

⏱️ Time: O(n² log(max)) Space: O(1)

Instead of recalculating GCD from scratch for each subarray, maintain the GCD as we extend the subarray. When GCD becomes less than k, we can break early since GCD can only decrease or stay same.

Brute Force - Check All Subarrays — Algorithm Steps

Iterate through all starting positions
For each start, extend subarray to all possible endings
Calculate GCD of current subarray
Count subarrays with GCD = k

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Calculate GCD

Compute GCD for each subarray

Count Matches

Count subarrays with GCD = k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int solution(int* nums, int numsSize, int k) {
    int count = 0;
    
    // Check all possible subarrays
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            // Calculate GCD of subarray nums[i:j+1]
            int currentGcd = nums[i];
            for (int l = i + 1; l <= j; l++) {
                currentGcd = gcd(currentGcd, nums[l]);
            }
            
            if (currentGcd == k) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ']' && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops O(n²) for all subarrays, O(n) to calculate GCD each time

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for variables

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Subarrays With GCD Equal to K - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler