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
Solution (Java)
class Solution {
public int subarrayLCM(int[] nums, int k) {
for(int i = 0; i < nums.length ; i++){
if(k % nums[i] != 0){
nums[i] = -1;
}
}
int i = 0;
int j = 0;
int lc = 1;
int ans = 0;
while(j < nums.length){
if(nums[j] == -1){
i = i+1;
j = i;
lc = 1;
continue;
}
lc = lcm(nums[j],lc);
if(lc < k){
j++;
}else if(lc == k){
ans++;
j++;
if(j == nums.length){
i = i+1;
j = i;
lc = 1;
}
}else{
i = i+1;
j = i;
lc = 1;
}
}
return ans;
}
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// method to return LCM of two numbers
static int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).