LeetCode Problem 2470

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

LeetCode 2470, Number of Subarrays With LCM Equal to K

Problem Understanding

The problem gives us an integer array nums and an integer k. We must count how many contiguous subarrays have a least common multiple, LCM, exactly equal to k.

A subarray is any continuous segment of the array. For every possible subarray, we compute the LCM of all its elements. If that LCM equals k, we increment the answer.

The least common multiple of a set of integers is the smallest positive integer divisible by every number in the set. For example:

• LCM(2, 3) = 6
• LCM(3, 6) = 6
• LCM(2, 4) = 4

The constraints are relatively small:

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

Since the array length is only 1000, an O(n^2) solution is acceptable because there are at most about one million subarrays. However, an O(n^3) solution would become inefficient because recomputing the LCM from scratch for every subarray would add another factor of n.

Several edge cases are important:

• Elements larger than k can never participate in a valid subarray if they do not divide k
• Once the running LCM exceeds k, it can never decrease again
• A single element subarray may itself equal k
• Arrays containing 1 require careful handling because LCM(x,1) = x
• If no subarray has LCM equal to k, the answer should be 0

Understanding the monotonic behavior of LCM is the key observation for the optimal solution.

Approaches

Brute Force Approach

The brute force method considers every possible subarray. For each subarray, we recompute the LCM of all its elements from scratch.

Suppose we choose a starting index i and an ending index j. We iterate through all elements from i to j and compute the LCM incrementally. If the final LCM equals k, we count that subarray.

This approach is correct because it explicitly evaluates every possible subarray and directly checks the required condition.

However, the complexity is too high:

• There are O(n^2) subarrays
• Computing the LCM of each subarray from scratch takes O(n) time

Therefore, the total complexity becomes O(n^3).

With n = 1000, this can become too slow.

Optimal Approach

The key insight is that we do not need to recompute the LCM from scratch for every subarray.

When extending a subarray from left to right, we can maintain the running LCM incrementally:

$$LCM(a,b)=\frac{a \times b}{GCD(a,b)}$$

If we already know the LCM of nums[i..j-1], we can compute the LCM of nums[i..j] in constant time.

Another important observation is that the LCM can only stay the same or increase as we add more elements. It never decreases.

This gives us a powerful pruning condition:

• If the running LCM becomes greater than k, we can stop expanding the current subarray
• If k % current_lcm != 0, the current LCM can never become exactly k later

This reduces unnecessary work significantly.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Recomputes LCM for every subarray
Optimal	O(n² × log(max(nums)))	O(1)	Maintains incremental LCM and prunes early

Algorithm Walkthrough

Step 1: Define an LCM Helper Function

We need a helper to compute:

$$LCM(a,b)=\frac{a \times b}{GCD(a,b)}$$

We use the greatest common divisor because it avoids repeated factorization.

Step 2: Iterate Over All Starting Positions

For every index start, we begin forming subarrays starting at that position.

We initialize:

current_lcm = 1

This variable will store the LCM of the current subarray.

Step 3: Extend the Subarray to the Right

For every ending index end >= start, we update:

current_lcm = lcm(current_lcm, nums[end])

This efficiently maintains the LCM incrementally.

Step 4: Check Pruning Conditions

If either of these conditions becomes true:

current_lcm > k

or

k % current_lcm != 0

we stop exploring longer subarrays from this starting point.

This works because adding more numbers can only keep the LCM the same or increase it.

Step 5: Count Valid Subarrays

Whenever:

current_lcm == k

we increment the answer.

Step 6: Continue Until All Starts Are Processed

We repeat the process for every possible starting index and return the total count.

Why it works

The algorithm works because every subarray is explored exactly once through its starting and ending indices. The running LCM always correctly represents the LCM of the current subarray because:

$$LCM(a,b,c)=LCM(LCM(a,b),c)$$

The pruning conditions are valid because LCM is monotonic. Once the LCM exceeds k or stops dividing k, no future extension can ever bring it back to exactly k.

Python Solution

from typing import List
from math import gcd

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        def lcm(a: int, b: int) -> int:
            return (a * b) // gcd(a, b)

        n = len(nums)
        answer = 0

        for start in range(n):
            current_lcm = 1

            for end in range(start, n):
                current_lcm = lcm(current_lcm, nums[end])

                if current_lcm == k:
                    answer += 1

                if current_lcm > k or k % current_lcm != 0:
                    break

        return answer

The implementation begins by importing gcd from Python's math module. Since the LCM formula depends on GCD, this gives us an efficient and reliable primitive operation.

The helper function lcm(a, b) computes the least common multiple using the standard mathematical identity:

$$LCM(a,b)=\frac{a \times b}{GCD(a,b)}$$

The outer loop selects the starting index of the subarray. For every new start position, the running LCM is reset to 1.

The inner loop expands the subarray one element at a time. Instead of recomputing the LCM of the entire subarray, we update it incrementally using the previous result.

After each update, we check whether the current LCM equals k. If it does, we increment the answer.

The pruning condition is extremely important for efficiency. Once the current LCM exceeds k, or no longer divides k, further expansion is pointless because the LCM cannot decrease later.

Finally, the total number of valid subarrays is returned.

Go Solution

package main

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func lcm(a, b int) int {
	return (a * b) / gcd(a, b)
}

func subarrayLCM(nums []int, k int) int {
	n := len(nums)
	answer := 0

	for start := 0; start < n; start++ {
		currentLCM := 1

		for end := start; end < n; end++ {
			currentLCM = lcm(currentLCM, nums[end])

			if currentLCM == k {
				answer++
			}

			if currentLCM > k || k%currentLCM != 0 {
				break
			}
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version.

Go does not provide a built in gcd function, so we implement the Euclidean algorithm manually. The lcm helper uses integer arithmetic exactly like the Python solution.

Since the constraints are small, integer overflow is not a concern here because all values are at most 1000.

Slices in Go behave naturally for array traversal, so no special handling is needed for empty arrays because the problem guarantees at least one element.

Worked Examples

Example 1

Input:

nums = [3,6,2,7,1]
k = 6

We trace every starting index.

Start = 0

End	Subarray	Current LCM	Valid?
0	[3]	3	No
1	[3,6]	6	Yes
2	[3,6,2]	6	Yes
3	[3,6,2,7]	42	Stop

Current answer = 2

Start = 1

End	Subarray	Current LCM	Valid?
1	[6]	6	Yes
2	[6,2]	6	Yes
3	[6,2,7]	42	Stop

Current answer = 4

Start = 2

End	Subarray	Current LCM	Valid?
2	[2]	2	No
3	[2,7]	14	Stop

Start = 3

End	Subarray	Current LCM	Valid?
3	[7]	7	Stop

Start = 4

End	Subarray	Current LCM	Valid?
4	[1]	1	No

Final answer:

4

Example 2

Input:

nums = [3]
k = 2

Start = 0

End	Subarray	Current LCM	Valid?
0	[3]	3	Stop

The LCM already exceeds k, so no valid subarray exists.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² × log(max(nums)))	Two nested loops, each LCM computation requires GCD
Space	O(1)	Only a few variables are used

The outer loop runs n times, and the inner loop may also run up to n times in the worst case. Each iteration performs a GCD computation, which takes logarithmic time relative to the input values. Since all numbers are small, the practical runtime is very fast.

The algorithm uses constant extra memory because it only stores counters and the current LCM.

Test Cases

from typing import List

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        from math import gcd

        def lcm(a, b):
            return (a * b) // gcd(a, b)

        answer = 0
        n = len(nums)

        for start in range(n):
            current_lcm = 1

            for end in range(start, n):
                current_lcm = lcm(current_lcm, nums[end])

                if current_lcm == k:
                    answer += 1

                if current_lcm > k or k % current_lcm != 0:
                    break

        return answer

sol = Solution()

assert sol.subarrayLCM([3, 6, 2, 7, 1], 6) == 4  # official example
assert sol.subarrayLCM([3], 2) == 0  # single element mismatch
assert sol.subarrayLCM([6], 6) == 1  # single element exact match
assert sol.subarrayLCM([1, 1, 1], 1) == 6  # every subarray valid
assert sol.subarrayLCM([2, 3, 4], 12) == 1  # whole array only
assert sol.subarrayLCM([2, 2, 2], 2) == 6  # repeated equal elements
assert sol.subarrayLCM([5, 10, 20], 10) == 2  # overlapping valid subarrays
assert sol.subarrayLCM([7, 7, 7], 6) == 0  # no divisor relationship
assert sol.subarrayLCM([1, 2, 3], 6) == 1  # LCM formed gradually
assert sol.subarrayLCM([2, 6, 3], 6) == 4  # multiple valid ranges

Test Case Summary

Test	Why
[3,6,2,7,1], k=6	Verifies standard mixed behavior
[3], k=2	Verifies no valid subarray
[6], k=6	Tests single element success
[1,1,1], k=1	Every subarray should count
[2,3,4], k=12	Only full array works
[2,2,2], k=2	Repeated elements create many subarrays
[5,10,20], k=10	Tests overlapping valid windows
[7,7,7], k=6	Ensures pruning works correctly
[1,2,3], k=6	LCM accumulates over expansion
[2,6,3], k=6	Multiple distinct valid subarrays

Edge Cases

One important edge case occurs when k = 1. Since the LCM of any number greater than 1 cannot become 1, only subarrays consisting entirely of 1s are valid. This can easily expose bugs in implementations that incorrectly initialize the running LCM or mishandle multiplication. The implementation handles this naturally because the running LCM remains 1 only when all included elements are also 1.

Another important case occurs when an element does not divide k. For example, if k = 6 and we encounter 7, the running LCM immediately becomes incompatible with k. A naive solution might continue expanding the subarray unnecessarily. The pruning condition:

k % current_lcm != 0

correctly stops further processing immediately.

A third edge case involves repeated valid LCM values. Consider [2,2,2] with k = 2. Every possible subarray has LCM equal to 2. Some implementations accidentally skip counting overlapping subarrays or incorrectly reset the running LCM. The nested loop structure ensures every contiguous range is evaluated independently and counted correctly.

A fourth subtle case occurs when the running LCM exceeds k. Since LCM is monotonic, once it becomes larger than k, it can never shrink back down. Without this observation, the algorithm would waste time exploring impossible extensions. The implementation correctly terminates early in these situations, improving efficiency while preserving correctness.