##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2470.html

# 2470. Number of Subarrays With LCM Equal to K

• Difficulty: Medium.
• Related Topics: Array, Math, Number Theory.
• Similar Questions: Number of Subarrays With GCD Equal to K.

## 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 <= 1000

• 1 <= nums[i], k <= 1000

## Solution (Java, C++, Python)

• class Solution {
public int subarrayLCM(int[] nums, int k) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = nums[i];
for (int j = i; j < n; ++j) {
int b = nums[j];
int x = lcm(a, b);
if (x == k) {
++ans;
}
a = x;
}
}
return ans;
}

private int lcm(int a, int b) {
return a * b / gcd(a, b);
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}

• class Solution {
public:
int subarrayLCM(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = nums[i];
for (int j = i; j < n; ++j) {
int b = nums[j];
int x = lcm(a, b);
ans += x == k;
a = x;
}
}
return ans;
}
};

• 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


• 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)
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).