-
Notifications
You must be signed in to change notification settings - Fork 3
/
2411.cpp
48 lines (45 loc) · 1.41 KB
/
2411.cpp
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
46
47
48
class Solution {
public:
vector<bool> toBinary(int num) {
vector<bool> v(32, 0);
int index = 0;
while (num) {
if (num & 1) v[index] = true;
else v[index] = false;
index++;
num >>= 1;
}
return v;
}
bool isValid(vector<bool>& target, vector<int>& counting) {
for (int i = 0; i < 32; ++i) {
if (target[i]) {
if (counting[i] <= 0) return false;
}
}
return true;
}
vector<int> smallestSubarrays(vector<int>& nums) {
vector<vector<bool>> numsBinary;
for (auto& num : nums) numsBinary.push_back(toBinary(num));
vector<bool> target(32, false);
vector<int> counting(32, 0);
int n = nums.size();
vector<int> res(n, -1);
int right = n - 1;
for (int left = n - 1; left >= 0; --left) {
for (int i = 0; i < 32; ++i) {
target[i] = target[i] | numsBinary[left][i];
counting[i] += numsBinary[left][i];
}
while (isValid(target, counting) && right >= 0 && right >= left) {
for (int i = 0; i < 32; ++i) {
counting[i] -= numsBinary[right][i];
}
right--;
}
res[left] = (right + 1) - left + 1;
}
return res;
}
};