We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays With GCD Equal to K

Number: 2546

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and an integer k, count the number of contiguous subarrays in which the greatest common divisor (GCD) of all elements equals k.

Key Insights

  • A subarray is a contiguous segment of the array.
  • The problem requires computing the GCD for each subarray and checking if it is equal to k.
  • If the running GCD ever becomes less than k or is not divisible by k, further extension of that subarray will not yield a GCD equal to k. This can be used as an early break condition.
  • Using a brute-force two-loop approach is acceptable given that nums.length can be up to 1000.

Space and Time Complexity

Time Complexity: O(n² * log(max(nums))) – n² for all subarrays and log(max(nums)) for each GCD computation. Space Complexity: O(1) – only constant extra space is used.

Solution

The approach is to iterate over all possible subarrays using two nested loops. For each subarray starting at index i, update a running GCD as you extend the subarray one element at a time. If the current GCD equals k, increment the count. Additionally, if the running GCD becomes less than k or not divisible by k, break early from the inner loop since extending the subarray further will not yield a GCD equal to k. This simple approach leverages the property that adding more numbers can only decrease the GCD.

Code Solutions

from math import gcd

def subarrayGCD(nums, k):
    count = 0
    n = len(nums)
    # iterate through each possible starting index of a subarray
    for i in range(n):
        current_gcd = 0
        # extend the subarray one element at a time
        for j in range(i, n):
            current_gcd = gcd(current_gcd, nums[j])
            if current_gcd == k:
                count += 1
            # early exit condition if extended subarray cannot have GCD equal to k
            if current_gcd < k or current_gcd % k != 0:
                break
    return count

# Example usage:
nums = [9, 3, 1, 2, 6, 3]
k = 3
print(subarrayGCD(nums, k))  # Expected Output: 4
← Back to All Questions