Skip to main content
Talentd

Number of Subarrays With LCM Equal to K - Solution & Explanation

MediumArrayMathNumber Theory15 min readAsked at: Amazon, Google, Unity
Practice this problem

Problem Statement

Given an integer array nums and an integer k, return the number of subarrays of nums where the least common multiple of the subarray's elements is k.

A subarray is a contiguous non-empty sequence of elements within an array.

The least common multiple of an array is the smallest positive integer that is divisible by all the array elements.

 

Example 1:

Input: nums = [3,6,2,7,1], k = 6
Output: 4
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: You are given an integer array nums and an integer k. The task is to count how many contiguous subarrays have a Least Common Multiple (LCM) exactly equal to k. A subarray contributes to the answer only if the LCM of all its elements equals k.

Approach 1: Brute Force Enumeration (O(n² log k) time, O(1) space)

Start every subarray from index i and extend it to the right. Maintain the running LCM while iterating j from i to n-1. The LCM of two numbers is computed using lcm(a,b) = (a * b) / gcd(a,b). Each time the running LCM becomes exactly k, increment the answer. If the LCM exceeds k or k % currentLCM != 0, further expansion cannot produce k, so you stop early for that starting index. This direct enumeration checks all possible subarrays and works well for small inputs.

Approach 2: Optimized Expansion with Prefix LCM Pruning (O(n log k) time, O(1) space)

The key observation: if the current LCM ever becomes greater than k or is not a divisor of k, extending the subarray will never bring it back to k. Use the same outer loop for starting index i, but aggressively prune expansions based on this property. Maintain a running LCM while extending the subarray and stop immediately once the divisor condition fails. Because LCM values grow quickly, the inner loop usually runs only a few iterations, making the practical complexity close to linear. All LCM calculations rely on fast gcd operations from number theory.

This approach leverages properties of math and number theory to avoid exploring impossible states. The array itself is processed sequentially using simple iteration patterns common in array problems.

Recommended for interviews: Interviewers expect the optimized expansion approach. The brute force method demonstrates that you understand how to compute LCM incrementally across subarrays. The optimized version shows deeper insight into number theory constraints, specifically the observation that valid LCMs must divide k. That pruning reduces unnecessary checks and brings the complexity close to O(n log k), which is typically the intended solution.

Approach 1: Brute Force Approach

This approach involves iterating over all possible subarrays, calculating the Least Common Multiple (LCM) for each, and checking if it equals k. Though this is a straightforward way to tackle the problem, it is not the most efficient.

The code employs a double loop to iterate through all the subarrays. For each subarray, it calculates the LCM of its elements and checks if it equals the given number k. Whenever the LCM matches k, it increments the result count. The greatest common divisor (GCD) function is used to calculate the LCM efficiently.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of this approach is O(n^2) due to the double loop iterating over subarrays. The space complexity is O(1), as no additional space proportional to input size is used.

Try this approach in the editor →

Approach 2: Optimized Approach Using Prefix LCM

This approach involves using a prefix LCM concept to optimize the calculation of LCM over subarrays. By storing intermediate LCM values, we can reduce redundant computations, potentially yielding a more efficient solution.

This C implementation optimizes the LCM computation by maintaining a prefix array where the LCM up to each index is stored and reused for further calculations. This reduces the need to recompute LCMs from scratch for every potential subarray.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The approach improves the effective time complexity compared to the brute force method by using previously computed values, potentially avoiding some redundant calculations. The space complexity is O(n) due to the prefix array.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n^2). Here, n is the length of the array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

The time complexity of this approach is O(n^2) due to the double loop iterating over subarrays. The space complexity is O(1), as no additional space proportional to input size is used.

Optimized Approach Using Prefix LCM

The approach improves the effective time complexity compared to the brute force method by using previously computed values, potentially avoiding some redundant calculations. The space complexity is O(n) due to the prefix array.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n² log k)O(1)When constraints are small or when demonstrating the baseline logic for computing LCM across subarrays.
Optimized Prefix LCM Expansion with PruningO(n log k)O(1)General case and interview solution. Stops early when LCM exceeds k or stops dividing k.

Video Solution

2470. Number of Subarrays With LCM Equal to K | LeetCode Weekly Contest 319 | LeetCode 2471 • Bro Coders • 2,364 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Number of Subarrays With LCM Equal to K easy or hard?
The problem is rated Medium because the brute force idea is straightforward but the key optimization requires recognizing number theory constraints on LCM values. Understanding how LCM grows and when to prune the search is the main challenge.
Number of Subarrays With LCM Equal to K Python/Java solution
In Python or Java, iterate through each starting index and maintain a running LCM using the formula lcm(a,b) = (a*b)/gcd(a,b). Stop expanding the subarray if the LCM becomes larger than k or does not divide k. This optimized strategy runs in about O(n log k) time.
How to solve Number of Subarrays With LCM Equal to K in O(n)?
A strict O(n) worst-case solution is uncommon because each step involves GCD calculations while extending subarrays. The practical optimal approach is near-linear, around O(n log k), using incremental LCM updates and pruning whenever the current LCM exceeds k or stops dividing k.
What is the best approach for Number of Subarrays With LCM Equal to K?
The most effective solution expands each subarray while maintaining a running LCM and stops early when the LCM exceeds k or no longer divides k. This pruning drastically reduces unnecessary checks. The approach runs in roughly O(n log k) time because LCM values grow quickly and rely on efficient GCD calculations.
Is Number of Subarrays With LCM Equal to K asked at Google/Amazon/Meta?
Problems involving LCM, GCD, and subarray enumeration frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests number theory knowledge combined with efficient array iteration and pruning techniques.
What data structure is used in Number of Subarrays With LCM Equal to K?
The solution mainly uses arrays with iterative expansion of subarrays. No complex data structures are required. The core operations rely on number theory functions such as GCD and LCM calculations during traversal.
What is the time complexity of Number of Subarrays With LCM Equal to K?
The brute force approach runs in O(n² log k) because every subarray is explored and each step requires a GCD-based LCM calculation. The optimized solution prunes invalid expansions early, reducing the average complexity to about O(n log k) with constant auxiliary space.

Ready to solve this problem?

Practice Number of Subarrays With LCM Equal to K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Subarrays With GCD Equal to K