On a quick implementation of GCD - Greatest Common Divisor - Part II

Another example that requires a quick GCD implementation, back from Euclidian days. Despite the nested loops yielding an N^2 complexity, in addition to the LogN GCD (hence a time complexity of N^2 * LogN), N is relatively small (10^3) leading to a reasonable execution time. Code is below, cheers, ACC.

Number of Subarrays With GCD Equal to K - LeetCode

2447. Number of Subarrays With GCD Equal to K

Medium

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.

 

Example 1:

Input: nums = [9,3,1,2,6,3], k = 3
Output: 4
Explanation: The subarrays of nums where 3 is the greatest common divisor of all the subarray's elements are:
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

Example 2:

Input: nums = [4], k = 7
Output: 0
Explanation: There are no subarrays of nums where 7 is the greatest common divisor of all the subarray's elements.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 109

Accepted

10,534

Submissions

24,383

public class Solution {
    public int SubarrayGCD(int[] nums, int k)
    {
        int retVal = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            int gcd = nums[i];
            for (int j = i; j < nums.Length; j++)
            {
                gcd = GCD(gcd, nums[j]);
                if (gcd == k) retVal++;
                else if (gcd < k) break;
            }
        }
        return retVal;
    }

    public int GCD(int a, int b)
    {
        if (a == 0 || b == 0)
        {
            return 0;
        }

        while (b != 0)
        {
            int t = b;
            b = a % b;
            a = t;
        }

        return a;
    }
}