2470. Number of Subarrays With LCM Equal to K

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        unsigned int n= nums.size(), ret = 0;
        for(int i=0;i<n;++i)
        {
            unsigned int t = nums[i];
            for(int j=i;j<n;j++)
            {
                t= lcm(t, nums[j]);
                if(t==k) ret++;
            }
        }
        
        return ret;
    }
};

analysis

  • time complexity O(n^2)
  • space complexity O(1)