Number of Subarrays With LCM Equal to K

Problem

Given an integer array nums and an integer k, return _the number ofsubarrays 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.

Examples

Example 1

1
2
3
4
5
6
7


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

1
2
3


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

Method 1 – Brute Force with LCM

Intuition

Since n is small (≤ 1000), we can check all subarrays and compute their LCM. If the LCM equals k, count it.

Approach

For each start index i, initialize lcm = 1.
For each end index j ≥ i, update lcm = lcm(lcm, nums[j]).
If lcm == k, increment answer. If lcm > k or k % nums[j] != 0, break early.
Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <numeric>
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            int lcm = 1;
            for (int j = i; j < n; ++j) {
                lcm = std::lcm(lcm, nums[j]);
                if (lcm == k) ans++;
                if (lcm > k) break;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func lcm(a, b int) int {
    return a / gcd(a, b) * b
}
func subarrayLCM(nums []int, k int) int {
    n, ans := len(nums), 0
    for i := 0; i < n; i++ {
        l := 1
        for j := i; j < n; j++ {
            l = lcm(l, nums[j])
            if l == k { ans++ }
            if l > k { break }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int lcm = 1;
            for (int j = i; j < n; j++) {
                lcm = lcm(lcm, nums[j]);
                if (lcm == k) ans++;
                if (lcm > k) break;
            }
        }
        return ans;
    }
    private int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b; b = a % b; a = t;
        }
        return a;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    fun subarrayLCM(nums: IntArray, k: Int): Int {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        fun lcm(a: Int, b: Int): Int = a / gcd(a, b) * b
        var ans = 0
        for (i in nums.indices) {
            var l = 1
            for (j in i until nums.size) {
                l = lcm(l, nums[j])
                if (l == k) ans++
                if (l > k) break
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


from math import gcd
class Solution:
    def subarrayLCM(self, nums: list[int], k: int) -> int:
        def lcm(a, b):
            return a * b // gcd(a, b)
        n, ans = len(nums), 0
        for i in range(n):
            l = 1
            for j in range(i, n):
                l = lcm(l, nums[j])
                if l == k:
                    ans += 1
                if l > k:
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


impl Solution {
    pub fn subarray_lcm(nums: Vec<i32>, k: i32) -> i32 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b; b = a % b; a = t;
            }
            a
        }
        fn lcm(a: i32, b: i32) -> i32 {
            a / gcd(a, b) * b
        }
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n {
            let mut l = 1;
            for j in i..n {
                l = lcm(l, nums[j]);
                if l == k { ans += 1; }
                if l > k { break; }
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    subarrayLCM(nums: number[], k: number): number {
        function gcd(a: number, b: number): number {
            while (b !== 0) { [a, b] = [b, a % b] }
            return a
        }
        function lcm(a: number, b: number): number {
            return a / gcd(a, b) * b
        }
        let ans = 0, n = nums.length
        for (let i = 0; i < n; i++) {
            let l = 1
            for (let j = i; j < n; j++) {
                l = lcm(l, nums[j])
                if (l === k) ans++
                if (l > k) break
            }
        }
        return ans
    }
}

Complexity

⏰ Time complexity: O(n^2 log k)
🧺 Space complexity: O(1)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Brute Force with LCM#

Intuition#

Approach#

Code#

Complexity#