Posted on

## Submission

```class Solution {
bool checkOK(int l, int r, vector<vector<int>>& bitCounts) {
for(int i = 0; i < 32; ++i) {
if(bitCounts[l][i] && !(bitCounts[l][i] - bitCounts[r][i])) return false;
}
return true;
}
public:
vector<int> smallestSubarrays(vector<int>& nums) {
int n = nums.size();

vector<vector<int>> bitCounts(n + 1, vector<int>(32, 0));

for(int i = n - 1; i >= 0; --i) {
for(int j = 0; j < 32; ++j) {
if((nums[i]>>j)&1) bitCounts[i][j] = bitCounts[i+1][j] + 1;
else bitCounts[i][j] = bitCounts[i+1][j];
}
}

vector<int> rets(n);
for(int i = 0; i < n; ++i) {
int l = i + 1, r = n;
while(l < r) {
int mid = l + (r - l) / 2;
if(checkOK(i, mid, bitCounts)) r = mid;
else l = mid + 1;
}

rets[i] = l - i;
}

return rets;

}
};

// 1 01.  2 3
// 0  0.  2 2
// 2 10.  2 2
// 1  1.  1 2
// 3 11   1 1```
```class Solution {
bool removeOK(int x, vector<int>& count) {
for(int i = 0; i < 32; ++i) {
if(((x>>i)&1) && count[i] == 1) return false;
}
return true;
}
public:
vector<int> smallestSubarrays(vector<int>& nums) {
int n = nums.size();

vector<int> count(32, 0);
vector<int> rets(n);

int cur = n - 1;
for(int i = n - 1; i >= 0; --i) {
for(int j = 0; j < 32; ++j) {
count[j] += (nums[i]>>j)&1;
}

for(; cur > i && removeOK(nums[cur], count); cur--) {
for(int j = 0; j < 32; ++j) {
count[j] -= (nums[cur] >> j) & 1;
}
}

rets[i] = cur - i + 1;
}

return rets;
}
};
```