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 <= 1000
  • 1 <= nums[i], k <= 1000

二、分析

  • 1 <= nums.length <= 1000
  • 1 <= 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;

回目錄 Catalog