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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays With LCM Equal to K

Number: 2557

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and an integer k, return the number of contiguous subarrays of nums where the least common multiple (LCM) of the subarray’s elements is equal to k.

Key Insights

  • A valid subarray must consist only of numbers that are factors of k. If an element does not divide k, including it would introduce extra prime factors.
  • Use a sliding window (nested loop) approach. For every starting index, extend the subarray and update the LCM until it matches k.
  • Compute LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b) and use the Euclidean algorithm for the GCD.
  • Early break from the inner loop if an element does not divide k (or equivalently, if adding that element can no longer yield an LCM equal to k).

Space and Time Complexity

Time Complexity: O(n^2 * log(max(nums[i]))), where n is the length of nums, due to the nested loops and GCD computations. Space Complexity: O(1) additional space.

Solution

We iterate over each possible starting index of the subarray. For each start index, we maintain the current LCM of the subarray. For every new element, if the element is not a divisor of k, we break early because adding it would prevent the LCM from being k. We update the LCM using the formula LCM(a, b) = (a * b) / GCD(a, b). Whenever the updated LCM equals k, we increment our count.

Code Solutions

# Python solution with line-by-line comments

def gcd(a, b):
    # Compute the greatest common divisor using Euclid's algorithm.
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    # Compute the least common multiple using the formula.
    return a * b // gcd(a, b)

def subarrayLCM(nums, k):
    count = 0  # Counter for valid subarrays.
    n = len(nums)
    
    # Iterate over every possible starting index.
    for i in range(n):
        current_lcm = 1  # Initialize LCM for the subarray starting at index i.
        # Extend the subarray from the starting index.
        for j in range(i, n):
            # If the current number is not a divisor of k,
            # it will contribute extra factors making LCM != k.
            if k % nums[j] != 0:
                break
            # Update the running LCM with the current element.
            current_lcm = lcm(current_lcm, nums[j])
            # If the current LCM equals k, increment the counter.
            if current_lcm == k:
                count += 1
    return count

# Example usage:
# nums = [3,6,2,7,1], k = 6 should return 4
print(subarrayLCM([3,6,2,7,1], 6))
← Back to All Questions