Description

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;
    }
};