Number of Subarrays With LCM Equal to K — Problem & Solution
Number of Subarrays With LCM Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Subarrays With LCM Equal to K is a medium coding problem on arrays, math and number theory, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer k, return the number of subarrays (contiguous, non-empty) whose elements have a least common multiple equal to k.
The least common multiple of a set of numbers is the smallest positive integer divisible by every one of them.
Example 1
Input: nums = [2,6,3,1,4], k = 6
Output: 6
Explanation: `[2,6]`, `[2,6,3]`, `[2,6,3,1]`, `[6]`, `[6,3]` and `[6,3,1]`. Anything containing the `4` has LCM 12 or more.
Example 2
Input: nums = [7], k = 1
Output: 0
Constraints
1 <= nums.length <= 10001 <= nums[i], k <= 1000
Hints for Number of Subarrays With LCM Equal to K
Hint 1
Fix the left end and extend to the right, updating the LCM incrementally:
lcm(a, b) = a / gcd(a, b) * b.Hint 2
If some element does not divide
k, no subarray containing it can have LCMk.Hint 3
Stop extending as soon as the running LCM no longer divides
k— this also keeps every value at mostk, so nothing overflows.
How to solve Number of Subarrays With LCM Equal to K
The LCM of a growing subarray only grows (each new value is a multiple of the old one). Once it stops dividing k it can never come back to k, so each start only extends while the LCM is a divisor of k.
Approach
- For each start
i, setl = 1. - For
j = i..n-1, updatel = l / gcd(l, nums[j]) * nums[j]. - If
k % l != 0, break. - If
l == k, count the subarray.
Why it works
Extending a subarray replaces its LCM by a multiple of it. If l does not divide k, no multiple of l divides k either, so k is unreachable and breaking loses nothing. Before the break every l divides k, so it is at most k and the products stay small.
Complexity
- Time —
O(n^2 log k) - Space —
O(1)
Pitfalls
- Without the early break the LCM of a long subarray overflows 64-bit integers quickly.
- Divide before multiplying (
l / gcd * x) to keep the intermediate small. - Start the running LCM at 1, the identity for LCM.
Reference solution
Python
from typing import List
from math import gcd
def subarrayLCM(nums: List[int], k: int) -> int:
n = len(nums)
count = 0
for i in range(n):
l = 1
for j in range(i, n):
l = l // gcd(l, nums[j]) * nums[j]
if k % l != 0:
break
if l == k:
count += 1
return countJava
static int gcdLcm(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
public static int subarrayLCM(int[] nums, int k) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
int l = 1;
for (int j = i; j < n; j++) {
l = l / gcdLcm(l, nums[j]) * nums[j];
if (k % l != 0) break;
if (l == k) count++;
}
}
return count;
}C++
static int gcdLcm(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
int subarrayLCM(vector<int>& nums, int k) {
int n = nums.size(), count = 0;
for (int i = 0; i < n; i++) {
int l = 1;
for (int j = i; j < n; j++) {
l = l / gcdLcm(l, nums[j]) * nums[j];
if (k % l != 0) break;
if (l == k) count++;
}
}
return count;
}JavaScript
var subarrayLCM = function(nums, k) {
var gcd = function(a, b) {
while (b !== 0) { var t = a % b; a = b; b = t; }
return a;
};
var n = nums.length, count = 0;
for (var i = 0; i < n; i++) {
var l = 1;
for (var j = i; j < n; j++) {
l = l / gcd(l, nums[j]) * nums[j];
if (k % l !== 0) break;
if (l === k) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays