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

Although this problem doesn't necessarily ask for GCD, it requires it to calculate LCM (Least Common Multiple), which can be done via the formula LCM(a,b) = a*b/GCD(a,b). With that in hands we can solve this problem in N^2 given that N=10^3. Notice that once we calculate LCD(a,b) we can then use it as the carrier for the next number. Code is down below, cheers, ACC.

Number of Subarrays With LCM Equal to K - LeetCode

2470. Number of Subarrays With LCM Equal to K

Medium

Given an integer array nums and an integer k, return the number of subarrays of nums where the least common multiple of the subarray's elements is k.

A subarray is a contiguous non-empty sequence of elements within an array.

The least common multiple of an array is the smallest positive integer that is divisible by all the array elements.

 

Example 1:

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

Example 2:

Input: nums = [3], k = 2
Output: 0
Explanation: There are no subarrays of nums where 2 is the least common multiple of all the subarray's elements.

 

Constraints:

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

public class Solution {
    public int SubarrayLCM(int[] nums, int k)
    {
        int retVal = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            long lcm = nums[i];
            if (lcm == k) retVal++;
            for (int j = i + 1; j < nums.Length; j++)
            {
                lcm = (lcm * nums[j]) / GCD(lcm, nums[j]);
                if (lcm == k) retVal++;
                if (lcm > k) break;
            }
        }
        return retVal;
    }

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

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

        return a;
    }
}