Leetcode 2470: Number of Subarrays With LCM Equal to K

Input: You are given an integer array `nums` and an integer `k`. The array contains integers and `k` is the target LCM value.

Example: nums = [2, 3, 6, 4, 1], k = 6

Constraints:

• 1 <= nums.length <= 1000

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

Output: Return the number of subarrays where the LCM of the elements is equal to `k`.

Example: Output: 3

Constraints:

• The output should be an integer count.

Goal: The goal is to find subarrays where the LCM of the elements is exactly equal to `k`.

Steps:

• Iterate over all possible subarrays of `nums`.

• For each subarray, calculate the LCM of its elements.

• If the LCM equals `k`, increase the count.

Goal: The value of `k` and each element in `nums` are between 1 and 1000. The length of `nums` is between 1 and 1000.

Steps:

• 1 <= nums.length <= 1000

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

Assumptions:

• The input array `nums` will not be empty.

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

• Explanation: In this case, there are three subarrays where the LCM equals 6: [2, 3, 6], [3, 6], and [6].

Approach: To solve this problem, iterate through all possible subarrays and compute the LCM for each one, checking if it matches `k`.

Observations:

• We need to efficiently calculate the LCM of subarrays and check if it equals `k`.

• The LCM calculation for each subarray should be optimized to avoid redundant computations.

Steps:

• Start with an outer loop to iterate over the starting index of subarrays.

• Use an inner loop to calculate the LCM of elements from the starting index to the end of the array.

• For each subarray, if the LCM equals `k`, increment the count.

Empty Inputs:

• The input array `nums` will not be empty as per the problem constraints.

Large Inputs:

• For large input arrays, the solution should be efficient enough to avoid timeouts.

Special Values:

• If `k` is smaller than the smallest element in `nums`, the result should be 0.

Constraints:

• The solution should handle cases where `nums` contains a mix of large and small numbers efficiently.

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

1 : Function Declaration

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

The function `subarrayLCM` is declared, taking a reference to a vector of integers `nums` and an integer `k`. It will return an integer representing the count of subarrays whose LCM equals `k`.

2 : Variable Initialization

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

The variable `n` stores the size of the `nums` vector, and `cnt` is initialized to zero to track the number of valid subarrays where the LCM equals `k`.

3 : Outer Loop

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

The outer loop starts, iterating through each element of the `nums` vector. The variable `i` represents the starting index of the subarray.

4 : Inner Loop

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

The inner loop starts at index `i` and continues as long as the condition `k % nums[j] == 0` is true, meaning the current number divides `k`. The variable `j` represents the ending index of the subarray.

5 : LCM Update

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

This line calculates the LCM of `nums[i]` and `nums[j]` using the formula `LCM(a, b) = (a * b) / GCD(a, b)` and stores the result back in `nums[i]`.

6 : Count Match

            cnt += nums[i] == k;

If the LCM of the current subarray is equal to `k`, `cnt` is incremented by 1.

7 : Return Statement

    return cnt;

The function returns the final count `cnt`, which represents the number of subarrays whose LCM equals `k`.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: The time complexity is O(n^2) because we check all subarrays, and for each subarray, we compute the LCM, which can take linear time.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant, as we only need a few variables to store intermediate results.

Leetcode 2470: Number of Subarrays With LCM Equal to K

Explore →