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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays With GCD Equal to K

Difficulty: Medium

Problem Description

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.

Key Insights

  • A subarray's GCD can only be equal to k if all elements in that subarray are multiples of k.
  • We can simplify the problem by dividing all elements in nums by k and counting the subarrays with a GCD of 1 in the transformed array.
  • To find the subarrays with a GCD of 1, we can use the Euclidean algorithm and maintain a running GCD as we expand the subarray.

Space and Time Complexity

Time Complexity: O(n^2) - We may need to check all pairs of start and end indices for subarrays. Space Complexity: O(1) - No additional space is used that scales with input size.

Solution

To solve the problem, we will:

  1. Traverse the array to identify subarrays whose elements are all multiples of k.
  2. For each valid starting index of a subarray, expand the subarray and compute the GCD of its elements.
  3. Count how many times the GCD equals 1 for those subarrays.
  4. Return the total count of subarrays where the GCD equals k.

Code Solutions

def countSubarraysWithGCD(nums, k):
    count = 0
    n = len(nums)
    
    for i in range(n):
        current_gcd = 0
        for j in range(i, n):
            # Check if nums[j] is a multiple of k
            if nums[j] % k != 0:
                break
            # Update the GCD
            current_gcd = gcd(current_gcd, nums[j] // k)
            # If GCD equals 1 (in the transformed array)
            if current_gcd == 1:
                count += 1
    return count

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
← Back to All Questions