Number of Subarrays With LCM Equal to K solution and explanation
Google
8 more videos on this problem
2470. Number of Subarrays With LCM Equal to K | LeetCode Weekly Contest 319 | LeetCode 2471Bro Coders · 10:23 · 2K views
Leetcode Weekly contest 319 - Medium - Number of Subarrays With LCM Equal to KPrakhar Agrawal · 5:38 · 732 views
2470. Number of Subarrays With LCM Equal to K (Leetcode Medium)Programming Live with Larry · 9:59 · 600 views
2470. Number of Subarrays With LCM Equal to K | Leetcode | Arrays | FundamentalsCoding with Tamilarasan · 6:23 · 384 views
Number of Subarrays With LCM Equal to K || Problem No. - 2470 || Leetcode || Explainations || PythonCoding Munda · 8:47 · 314 views
Number of Subarrays With LCM Equal to K || LeetCode Weekly 319 || Medium || C++Priyanshi Porwal · 6:07 · 204 views
Leetcode Weekly Contest 319 | Number of Subarrays With LCM Equal to K | Medium | ExplainedCoding with Jenish · 3:15 · 164 views
2470. Number of Subarrays With LCM Equal to K || LeetCode Weekly Contest 319 || MediumAmit Maity · 5:06 · 145 views
Number of Subarrays With LCM Equal to K LeetCode Weekly Contest 319 #java #leetcode #codingAkash Dey · 1:05 · 39 views
The problem
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 <= 10001 <= 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.
import math
def subarraysWithLCM(nums, k):
count = 0
for i in range(len(nums)):
lcm_val = nums[i]
if lcm_val == k:
count += 1
for j in range(i + 1, len(nums)):
if lcm_val > k:
break
lcm_val = math.lcm(lcm_val, nums[j])
if lcm_val == k:
count += 1
return count
# Example usage
nums = [3, 6, 2, 7, 1]
k = 6
print(subarraysWithLCM(nums, k))import java.util.*;
public class Solution {
private static int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
private static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
public static int subarraysWithLCM(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; ++i) {
int lcmVal = nums[i];
if (lcmVal == k) count++;
for (int j = i + 1; j < nums.length; ++j) {
if (lcmVal > k) break;
lcmVal = lcm(lcmVal, nums[j]);
if (lcmVal == k) count++;
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {3, 6, 2, 7, 1};
int k = 6;
System.out.println(subarraysWithLCM(nums, k));
}
}#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int subarraysWithLCM(const vector<int>& nums, int k) {
int count = 0;
for (int i = 0; i < nums.size(); ++i) {
int lcmVal = nums[i];
if (lcmVal == k) count++;
for (int j = i + 1; j < nums.size(); ++j) {
if (lcmVal > k) break;
lcmVal = lcm(lcmVal, nums[j]);
if (lcmVal == k) count++;
}
}
return count;
}
int main() {
vector<int> nums = {3, 6, 2, 7, 1};
int k = 6;
cout << subarraysWithLCM(nums, k) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
const t = b;
b = a % b;
a = t;
}
return a;
}
function lcm(a, b) {
return (a / gcd(a, b)) * b;
}
function subarraysWithLCM(nums, k) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let lcmVal = nums[i];
if (lcmVal === k) count++;
for (let j = i + 1; j < nums.length; j++) {
if (lcmVal > k) break;
lcmVal = lcm(lcmVal, nums[j]);
if (lcmVal === k) count++;
}
}
return count;
}
// Example usage
const nums = [3, 6, 2, 7, 1];
const k = 6;
console.log(subarraysWithLCM(nums, k));#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int subarraysWithLCM(int* nums, int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize; ++i) {
int lcmVal = nums[i];
if (lcmVal == k) count++;
for (int j = i + 1; j < numsSize; ++j) {
if (lcmVal > k) break;
lcmVal = lcm(lcmVal, nums[j]);
if (lcmVal == k) count++;
}
}
return count;
}
int main() {
int nums[] = {3, 6, 2, 7, 1};
int k = 6;
printf("%d\n", subarraysWithLCM(nums, 5, k));
return 0;
}using System;
class Solution {
private static int GCD(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
private static int LCM(int a, int b) {
return a / GCD(a, b) * b;
}
public static int SubarraysWithLCM(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.Length; ++i) {
int lcmVal = nums[i];
if (lcmVal == k) count++;
for (int j = i + 1; j < nums.Length; ++j) {
if (lcmVal > k) break;
lcmVal = LCM(lcmVal, nums[j]);
if (lcmVal == k) count++;
}
}
return count;
}
static void Main() {
int[] nums = { 3, 6, 2, 7, 1 };
int k = 6;
Console.WriteLine(SubarraysWithLCM(nums, k));
}
}This Python solution uses the math.lcm function from the Python standard library to calculate the LCM of numbers in each subarray. It iterates through all possible subarrays and checks if any have the LCM equal to k.
The time complexity is O(n^2) due to the examination of all subarray options. It requires O(1) space aside from some temporary variables.
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.
import math
def subarraysWithLCMPrefix(nums, k):
count = 0
prefix = [0] * len(nums)
for i in range(len(nums)):
prefix[i] = nums[i]
if prefix[i] == k:
count += 1
for j in range(i - 1, -1, -1):
prefix[j] = math.lcm(prefix[j], nums[i])
if prefix[j] == k:
count += 1
return count
# Example usage
nums = [3, 6, 2, 7, 1]
k = 6
print(subarraysWithLCMPrefix(nums, k))import java.util.*;
public class Solution {
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
private static int lcm(int a, int b) {
return (int) ((long) a / gcd(a, b) * b);
}
public static int subarraysWithLCMPrefix(int[] nums, int k) {
int count = 0;
int[] prefix = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
prefix[i] = nums[i];
if (prefix[i] == k) count++;
for (int j = i - 1; j >= 0; --j) {
prefix[j] = lcm(prefix[j], nums[i]);
if (prefix[j] == k) count++;
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {3, 6, 2, 7, 1};
int k = 6;
System.out.println(subarraysWithLCMPrefix(nums, k));
}
}#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int subarraysWithLCMPrefix(vector<int>& nums, int k) {
int count = 0;
vector<int> prefix(nums.size());
for (int i = 0; i < nums.size(); ++i) {
prefix[i] = nums[i];
if (prefix[i] == k) count++;
for (int j = i - 1; j >= 0; --j) {
prefix[j] = lcm(prefix[j], nums[i]);
if (prefix[j] == k) count++;
}
}
return count;
}
int main() {
vector<int> nums = {3, 6, 2, 7, 1};
int k = 6;
cout << subarraysWithLCMPrefix(nums, k) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
const t = b;
b = a % b;
a = t;
}
return a;
}
function lcm(a, b) {
return (a / gcd(a, b)) * b;
}
function subarraysWithLCMPrefix(nums, k) {
let count = 0;
let prefix = new Array(nums.length);
for (let i = 0; i < nums.length; i++) {
prefix[i] = nums[i];
if (prefix[i] === k) count++;
for (let j = i - 1; j >= 0; j--) {
prefix[j] = lcm(prefix[j], nums[i]);
if (prefix[j] === k) count++;
}
}
return count;
}
// Example usage
const nums = [3, 6, 2, 7, 1];
const k = 6;
console.log(subarraysWithLCMPrefix(nums, k));#include <stdio.h>
#include <stdbool.h>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
bool isLCMPrefix(int* prefix, int size, int k) {
for (int i = 0; i < size; ++i) {
if (lcm(prefix[i], k) == k) return true;
}
return false;
}
int subarraysWithLCMPrefix(int* nums, int numsSize, int k) {
int count = 0;
int prefix[numsSize];
for (int i = 0; i < numsSize; ++i) {
prefix[i] = nums[i];
if (prefix[i] == k) count++;
for (int j = i - 1; j >= 0; --j) {
prefix[j] = lcm(prefix[j], nums[i]);
if (prefix[j] == k) count++;
}
}
return count;
}
int main() {
int nums[] = {3, 6, 2, 7, 1};
int k = 6;
printf("%d\n", subarraysWithLCMPrefix(nums, 5, k));
return 0;
}using System;
class Solution {
private static int GCD(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
private static int LCM(int a, int b) {
return a / GCD(a, b) * b;
}
public static int SubarraysWithLCMPrefix(int[] nums, int k) {
int count = 0;
int[] prefix = new int[nums.Length];
for (int i = 0; i < nums.Length; ++i) {
prefix[i] = nums[i];
if (prefix[i] == k) count++;
for (int j = i - 1; j >= 0; --j) {
prefix[j] = LCM(prefix[j], nums[i]);
if (prefix[j] == k) count++;
}
}
return count;
}
static void Main() {
int[] nums = { 3, 6, 2, 7, 1 };
int k = 6;
Console.WriteLine(SubarraysWithLCMPrefix(nums, k));
}
}This Python code stores intermediary LCM values in a prefix list as it iterates through the array, allowing it to quickly evaluate each subarray's LCM for comparison against k.
This refined approach optimizes calculations by reusing stored results. The space complexity is O(n) for the prefix list.
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.
func subarrayLCM(nums []int, k int) (ans int) {
for i, a := range nums {
for _, b := range nums[i:] {
x := lcm(a, b)
if x == k {
ans++
}
a = x
}
}
return
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
func lcm(a, b int) int {
return a * b / gcd(a, b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n^2) due to the examination of all subarray options. It requires O(1) space aside from some temporary variables. |
| Optimized Approach Using Prefix LCM | This refined approach optimizes calculations by reusing stored results. The space complexity is O(n) for the prefix list. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(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 Pruning | O(n log k) | O(1) | General case and interview solution. Stops early when LCM exceeds k or stops dividing k. |
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.