#2470

Medium

LeetCode Problem Workspace

Number of Subarrays With LCM Equal to K

Find the number of subarrays in an array where the least common multiple (LCM) of the subarray equals a given integer k.

array math number theory

Problem Statement

You are given an integer array nums and an integer k. Your task is to return the number of contiguous subarrays of nums where the least common multiple (LCM) of the elements is exactly k.

A subarray is a contiguous, non-empty sequence of elements within an array. You should calculate the LCM for each subarray and check if it equals k.

Examples

Example 1

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

Output: 4

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

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

Solution Approach

Brute Force Approach

The simplest method is to generate all possible subarrays of the given array and calculate the LCM for each subarray. If the LCM matches k, increment the count. While this approach has a time complexity of O(n^2) due to the need to generate subarrays, it is a good starting point for small inputs.

Efficient LCM Calculation

To improve efficiency, we can optimize the LCM computation by maintaining a running LCM as we expand the subarray. This avoids recalculating the LCM for each subarray from scratch. With this optimization, we only need to check the LCM as we iterate through the array.

Early Termination

While expanding subarrays, if at any point the running LCM exceeds k, we can terminate further expansion for that subarray. This optimization reduces unnecessary computations, improving performance by stopping at the earliest failure condition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force approach has a time complexity of O(n^2) due to the need to evaluate each possible subarray. Optimizations like early termination and maintaining a running LCM reduce redundant calculations but still may require checking each possible subarray in the worst case.

What Interviewers Usually Probe

Ensure the candidate is familiar with the properties of the least common multiple and its efficient calculation.
Watch for optimization approaches and the candidate's awareness of trade-offs between brute force and optimized solutions.
Evaluate how well the candidate adapts their approach based on problem constraints, especially in terms of optimizing subarray checks.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the LCM computation by recalculating it for every subarray from scratch.
Not accounting for early termination when the running LCM exceeds k.
Misunderstanding the problem by assuming any number divisible by k is valid, when the LCM of the subarray must exactly equal k.

Follow-up variants

What if the array size is larger than the given constraints?
How would this problem change if negative numbers were allowed in the array?
What if instead of LCM, we needed to check for the greatest common divisor (GCD) of subarrays instead?

FAQ

What is the core challenge in the Number of Subarrays With LCM Equal to K problem?

The core challenge is efficiently calculating the LCM of subarrays and counting the ones where the LCM equals the given integer k.

How can I optimize my solution for the Number of Subarrays With LCM Equal to K problem?

Optimizing involves maintaining a running LCM while expanding subarrays, and terminating early when the LCM exceeds k.

Can I use brute force to solve the Number of Subarrays With LCM Equal to K problem?

Yes, brute force can work for small inputs, but it may not be efficient for larger arrays due to the O(n^2) complexity.

How does the Number of Subarrays With LCM Equal to K problem relate to number theory?

The problem involves calculating the least common multiple (LCM), a key concept in number theory, and understanding how LCM behaves in subarrays.

What is a common mistake when solving the Number of Subarrays With LCM Equal to K problem?

A common mistake is recalculating the LCM for each subarray from scratch, instead of maintaining a running LCM for optimization.

terminal

Solution

Solution 1: Enumeration

Enumerate each number as the first number of the subarray, and then enumerate each number as the last number of the subarray. Calculate the least common multiple of this subarray. If the least common multiple equals $k$, then increment the answer by one.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            a = nums[i]
            for b in nums[i:]:
                x = lcm(a, b)
                ans += x == k
                a = x
        return ans

Continue Practicing

#2447 number of subarrays with gcd equal to k #2521 distinct prime factors of product of array #2584 split the array to make coprime products