2470. Number of Subarrays With LCM Equal to K

2470. Number of Subarrays With LCM Equal to K (Medium)

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

Related Topics:
Array, Math, Number Theory

Similar Questions:

• Number of Subarrays With GCD Equal to K (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/number-of-subarrays-with-lcm-equal-to-k
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int subarrayLCM(vector<int>& A, int k) {
        int N = A.size(), ans = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = i, c = 1; j < N && c <= k; ++j) {
                c = lcm(A[j], c);
                ans += c == k;
            }
        }
        return ans;
    }
};