Problem Description

You are given an integer array nums and an integer k. Your task is to find how many subarrays have a least common multiple (LCM) equal to k.

A subarray is a contiguous sequence of elements from the array (cannot be empty). For example, if nums = [1, 2, 3], then [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3] are all valid subarrays.

The least common multiple of an array is the smallest positive integer that can be divided evenly by all elements in that array. For instance, the LCM of [2, 3] is 6 because 6 is the smallest number divisible by both 2 and 3.

The solution uses a nested loop approach. For each starting position i in the array, it considers all possible subarrays beginning at that position. It maintains a running LCM value a that gets updated as each new element b is included in the subarray. The LCM is calculated using the built-in lcm() function. Whenever the LCM equals k, the answer counter is incremented. This process continues for all possible subarrays, and the final count is returned.

The time complexity is O(n²) where n is the length of the array, since we examine all possible subarrays. The key insight is that we can efficiently compute the LCM of each subarray by updating the previous LCM value rather than recalculating from scratch.

Intuition

When we need to find subarrays with a specific property, a natural starting point is to check all possible subarrays. Since a subarray is defined by its starting and ending positions, we can use two nested loops to generate all combinations.

The key observation is that the LCM has an interesting property: as we extend a subarray by adding one more element, we can compute the new LCM using the previous LCM and the new element. We don't need to recalculate the LCM from scratch for the entire subarray. This is because LCM(a, b, c) = LCM(LCM(a, b), c).

Another important insight is that the LCM of a subarray will either stay the same or increase as we add more elements (it never decreases). This is because the LCM must be divisible by all elements, so adding a new element can only make it larger or keep it the same. Once the LCM exceeds k, we could potentially optimize by breaking early since it will never come back down to k.

The brute force approach works well here because:

1. We need to check every subarray anyway to count exact matches with k
2. The LCM calculation can be done incrementally as we extend each subarray
3. The problem likely has reasonable constraints on array size

By fixing the starting position and incrementally extending the subarray while updating the LCM, we efficiently explore all possibilities and count those where LCM == k.

Learn more about Math patterns.

Solution Approach

The solution uses an enumeration strategy to check all possible subarrays. Here's how the implementation works:

1. Outer Loop - Starting Position: We iterate through each index i from 0 to n-1 as the starting position of our subarray. This ensures we consider all possible starting points.

2. Initialize LCM Tracker: For each starting position i, we initialize variable a with nums[i]. This variable will track the running LCM of the current subarray.

3. Inner Loop - Extending Subarray: We iterate through elements from position i to the end of the array using nums[i:]. Each element b represents a potential ending element of our subarray.

4. LCM Calculation: For each new element b, we calculate x = lcm(a, b). This gives us the LCM of the subarray from position i to the current element's position. The lcm() function efficiently computes the least common multiple of two numbers.

5. Check and Count: We check if x == k. If true, we increment our answer counter by 1 using the expression ans += x == k (which adds 1 when True, 0 when False).

6. Update Running LCM: We update a = x to prepare for the next iteration. This allows us to incrementally build the LCM rather than recalculating from scratch.

The algorithm examines subarrays in the following order for an array [a, b, c]:

• Start at a: check [a], then [a,b], then [a,b,c]
• Start at b: check [b], then [b,c]
• Start at c: check [c]

This systematic approach ensures we count every subarray exactly once and efficiently compute their LCMs using the previous result.

Example Walkthrough

Let's walk through the solution with nums = [6, 2, 3] and k = 6.

Starting at index 0 (element 6):

• Initialize a = 6 (first element)
• Subarray [6]: Calculate x = lcm(6, 6) = 6. Since x == k (6 == 6), increment counter: ans = 1. Update a = 6.
• Subarray [6, 2]: Calculate x = lcm(6, 2) = 6. Since x == k (6 == 6), increment counter: ans = 2. Update a = 6.
• Subarray [6, 2, 3]: Calculate x = lcm(6, 3) = 6. Since x == k (6 == 6), increment counter: ans = 3. Update a = 6.

Starting at index 1 (element 2):

• Initialize a = 2 (first element)
• Subarray [2]: Calculate x = lcm(2, 2) = 2. Since x != k (2 != 6), no increment. Update a = 2.
• Subarray [2, 3]: Calculate x = lcm(2, 3) = 6. Since x == k (6 == 6), increment counter: ans = 4. Update a = 6.

Starting at index 2 (element 3):

• Initialize a = 3 (first element)
• Subarray [3]: Calculate x = lcm(3, 3) = 3. Since x != k (3 != 6), no increment. Update a = 3.

Final answer: 4 subarrays have LCM equal to 6

The key insight demonstrated here is how we efficiently compute the LCM incrementally. For instance, when extending [6] to [6, 2], we don't recalculate from scratch but use lcm(6, 2) where 6 was our previous LCM. This incremental approach allows us to check all subarrays in O(n²) time while maintaining the running LCM value.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code uses two nested loops to examine all subarrays:

• The outer loop runs n times (from i = 0 to n-1)
• For each iteration i, the inner loop iterates through nums[i:], which means:
  • When i = 0: inner loop runs n times
  • When i = 1: inner loop runs n-1 times
  • When i = n-1: inner loop runs 1 time
• Total iterations: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Within each iteration, the lcm(a, b) operation can be considered O(log(min(a,b))) in the worst case (using GCD calculation via Euclidean algorithm), but since the problem likely has bounded integer values, we can treat this as O(1) for practical purposes.

Therefore, the overall time complexity is O(n²).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables n, ans, i, a, b, and x each use O(1) space
• No additional data structures are created
• The iteration through nums[i:] doesn't create a new array, it just iterates through the existing array

The space complexity is O(1) (constant space).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. LCM Overflow and Early Termination

One critical pitfall in this solution is not properly handling the case where the LCM grows beyond k. Once the LCM of a subarray exceeds k, extending that subarray further will never reduce the LCM back to k (since LCM can only increase or stay the same when adding elements). The code includes an optimization with if current_lcm > k: break, but there's a subtlety here.

Problem: If k is not divisible by an element in the array, the LCM will never equal k for any subarray containing that element.

Example: If nums = [3, 6, 2] and k = 6:

• Starting at index 0: LCM([3]) = 3, LCM([3,6]) = 6 ✓, LCM([3,6,2]) = 6 ✓
• But if nums = [3, 7, 2] and k = 6:
• Starting at index 0: LCM([3]) = 3, LCM([3,7]) = 21 > 6 (breaks correctly)

Better approach: Add an additional check before processing:

# Optimization: k must be divisible by every element in a valid subarray
for start_idx in range(n):
    if k % nums[start_idx] != 0:
        continue  # Skip this starting position entirely
    current_lcm = nums[start_idx]
    # ... rest of the logic

2. Integer Overflow in LCM Calculation

The LCM calculation a * b // gcd(a, b) can cause integer overflow when a and b are large, even if their LCM would fit in an integer.

Problem: Multiplying two large numbers before division can exceed integer limits.

Solution: Check for potential overflow or add bounds:

def lcm(a: int, b: int) -> int:
    g = gcd(a, b)
    # Check if multiplication would overflow
    if a > k or b > k:  # LCM will definitely exceed k
        return k + 1  # Return any value > k to trigger early termination
    return (a // g) * b  # Divide first to reduce overflow risk

3. Missing Edge Case: Single Element Subarrays

While the current implementation handles single-element subarrays correctly, a common mistake when modifying this code is to accidentally skip them by starting the inner loop at start_idx + 1 instead of start_idx.

Incorrect modification:

for end_idx in range(start_idx + 1, n):  # Wrong! Skips single elements
    current_lcm = lcm(current_lcm, nums[end_idx])

Correct approach (as in the original):

for num in nums[start_idx:]:  # Includes single element subarrays

4. Inefficient LCM Recalculation

A tempting but inefficient approach would be to recalculate the LCM from scratch for each subarray:

Inefficient:

for i in range(n):
    for j in range(i, n):
        subarray_lcm = nums[i]
        for k in range(i+1, j+1):  # Recalculating from scratch
            subarray_lcm = lcm(subarray_lcm, nums[k])

The original solution correctly maintains a running LCM, which is much more efficient.