2470. Number of Subarrays With LCM Equal to K
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Array、Math、Number Theory - \(\color{blue}\textsf{weekly Contest 319}\)
一、題目
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
二、分析
1 <= nums.length <= 10001 <= nums[i], k <= 1000
三、解題
1. Brute Method
- Time complexity: \(O(n^2)\)
- Space complexity: \(O(1)\)
int subarrayLCM(vector<int>& nums, int k) {
int res = 0;
int n = nums.size();
int left = 0;
while (left < n) {
int right = left;
int tmp = 1; // 從 left 到 right 的公倍數
while (right < n) {
if (k % nums[right] == 0) { // 可被 k 整除才可能公倍數為 k
tmp = lcm(tmp, nums[right]);
if (tmp == k) res++;
} else {
break;
}
right++;
}
left++;
}
return res;
}2. Hash Table
- Time complexity: \(O(n^2)\)
- Space complexity: \(O(n)\)
int subarrayLCM(vector<int>& nums, int k) {
int res = 0;
int n = nums.size();
unordered_map<int,int> u;
for (int i = 0; i < n; i++) {
u[nums[i]]++;
unordered_map<int,int> v; // 到 i 為止可以被 k 整除的個數
for (auto [d, cnt] : u) {
int tmp = lcm(nums[i], d);
if (tmp == k) res += cnt; // 若公倍數等於 k 則加入答案
if (k % tmp == 0) v[tmp] += cnt;
}
swap(u, v); // 將可能的候選再加入下一輪繼續
}
return res;