4032. Longest Subarray With at Most K Distinct Prime Factors
You are given an integer array nums consisting of positive integers and an integer k.
The prime factor set of a subarray is the union of the distinct prime factors of all its elements.
Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
int factor[101010];
bool fl = false;
void init() {
if(fl) return;
for(int i = 2; i < 101010; i++) {
if(factor[i]) continue;
for(int j = i; j < 101010; j += i) {
factor[j] = i;
}
}
}
unordered_set<int> get(int x) {
unordered_set<int> us;
while(x > 1) {
int d = factor[x];
us.insert(d);
while(x % d == 0) x /= d;
}
return us;
}
class Solution {
public:
int longestSubarray(vector<int>& nums, int k) {
int res = -1, l = 0, r = 0, n = nums.size();
init();
unordered_map<int,int> mp;
auto op = [&](unordered_set<int>& us, int o) {
for(auto& u : us) {
mp[u] += o;
if(mp[u] == 0) mp.erase(u);
}
};
while(r < n) {
auto u = get(nums[r++]);
op(u,1);
while(mp.size() > k) {
auto u = get(nums[l++]);
op(u,-1);
}
res = max(res, r - l);
}
return res;
}
};
|
