Leetcode 2447: Number of Subarrays With GCD Equal to K

Input: The input consists of an array `nums` and an integer `k`.

Example: nums = [6, 3, 9, 12], k = 3

Constraints:

• 1 <= nums.length <= 1000

• 1 <= nums[i], k <= 10^9

Output: Return the number of subarrays where the greatest common divisor of all elements is equal to `k`.

Example: Output: 3

Constraints:

• All elements in the array are non-negative integers.

Goal: To find subarrays whose GCD equals `k`.

Steps:

• Iterate through the array to find subarrays.

• For each subarray, calculate the GCD of the elements.

• Count the subarrays where the GCD is equal to `k`.

Goal: The values of elements in `nums` and `k` are large, but within manageable limits.

Steps:

• The array `nums` contains up to 1000 elements.

• Each element in `nums` and `k` is between 1 and 10^9.

Assumptions:

• The GCD operation can handle large values efficiently.

• The subarrays are contiguous.

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

• Explanation: The subarrays where the GCD of elements is 3 are [9, 3], [3], [3, 1, 6], and [9, 3, 1, 6]. Hence, the answer is 4.

• Input: nums = [10, 20, 30, 40], k = 5

• Explanation: The subarrays where the GCD of elements is 5 are [10, 20, 30, 40], [10, 20], [20, 30], and [30, 40]. So, the answer is 4.

Approach: The problem can be solved by iterating through all possible subarrays, calculating the GCD of each subarray, and counting the subarrays that have a GCD equal to `k`.

Observations:

• We need an efficient way to compute GCDs for subarrays.

• Naively checking all subarrays might lead to high computational overhead for larger arrays.

• We can use a nested loop to generate all subarrays, compute their GCD, and check if it matches `k`.

Steps:

• 1. Initialize a counter variable to track the number of valid subarrays.

• 2. For each starting index of a subarray, iterate through the array to form subarrays.

• 3. For each subarray, calculate the GCD of its elements using a built-in function.

• 4. If the GCD is equal to `k`, increment the counter.

• 5. Return the counter as the result.

Empty Inputs:

• Input will never be empty as per the problem constraints.

Large Inputs:

• When the array is large (close to 1000 elements), the time complexity should be kept in mind.

Special Values:

• When `k` is larger than all elements in the array, there will be no subarrays with GCD equal to `k`.

Constraints:

• We assume the time complexity is efficient enough to handle the constraints provided.


int subarrayGCD(vector<int>& nums, int k) {        
    int cnt = 0, n = nums.size();
    
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n && nums[j] % k == 0; j++) {
            nums[i] = __gcd(nums[i], nums[j]);
            cnt += (nums[i] == k);
        }
    }
    return cnt;
}

1 : Function Definition

int subarrayGCD(vector<int>& nums, int k) {

This line defines the function `subarrayGCD`, which takes a vector of integers `nums` and an integer `k`, and returns the count of subarrays whose GCD equals `k`.

2 : Variable Initialization

    int cnt = 0, n = nums.size();

This line initializes the counter `cnt` to 0, which will track the number of valid subarrays, and `n`, which stores the size of the input array `nums`.

3 : Outer Loop

    for(int i = 0; i < n; i++) {

The outer loop starts at index `i` and iterates through each element of the array `nums`.

4 : Inner Loop Condition

        for(int j = i; j < n && nums[j] % k == 0; j++) {

The inner loop starts at index `i` and continues as long as the current element `nums[j]` is divisible by `k`. This ensures that we only consider elements that can potentially form a valid subarray.

5 : GCD Calculation

            nums[i] = __gcd(nums[i], nums[j]);

This line computes the greatest common divisor (GCD) of `nums[i]` and `nums[j]` and stores it back in `nums[i]`. This process updates the GCD as we extend the subarray.

6 : Count Increment

            cnt += (nums[i] == k);

If the GCD of the current subarray equals `k`, we increment the counter `cnt`.

7 : Return Statement

    return cnt;

This line returns the count `cnt` of valid subarrays whose GCD equals `k`.

Best Case: O(n)

Average Case: O(n^2 * log(max(nums)))

Worst Case: O(n^2 * log(max(nums)))

Description: In the worst case, we have to check all subarrays, and computing GCD for each subarray takes logarithmic time relative to the values involved.

Best Case: O(1)

Worst Case: O(1)

Description: We are only using a counter variable, so the space complexity is constant.

Leetcode 2447: Number of Subarrays With GCD Equal to K

Explore →