898. Bitwise ORs of Subarrays --- M !!!!

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results.  (Results that occur more than once are only counted once in the final answer.)

 

Example 1:

Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.

Example 2:

Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.

 

Note:

1. 1 <= A.length <= 50000
2. 0 <= A[i] <= 10^9

 

A:

首先思路是： 逐个  OR,  然后结果放到set里。   LTE了

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        int n = A.size();
        vector<int> V(A);
        unordered_set<int> S(A.begin(), A.end());
        for(int len = 2;len<=n; len++){
            for(int start = 0; start + len-1<n; start++){
                V[start] |= A[start+len-1];
                S.insert(V[start]);
            }
        }
        return S.size();
    }
};

试着 去重，依然不行。

考虑到最后可能很快都全 1 了，i.e. 2^32-1   弄个标志位，

思路像10块糖的一样. 然后做early stop check

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set<int> S(A.begin(),A.end()); 
        vector<int> V;
        for(int end = 1;end<A.size();end++){
            if(A[end] == A[end-1]) // skip duplicates
                continue;
            int v = A[end];    
            for(int j = end-1; j>=0;j--){
                v |= A[j];
                S.insert(v);
                if(v==INT_MAX)
                    break;
            }
        }
        return S.size();
    }
};

可是 依然LTE

那么every time, 我们不是加到之前所有的数。我们是加到，之前左右数的 OR 的集合。

因此，不需要跟之前所有的数去比较。 只需要比较前一个，保护A[end -1]的就好。

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set<int> S;
        vector<int> V;
        unordered_set<int> preSet{ 0 }; // initial as 0, so can OR with anyvalue
        for (int end = 0; end < A.size(); end++) {
            if (end > 0 && A[end] == A[end - 1]) // skip duplicates
                continue;
            int v = A[end];
            unordered_set<int> curSet{ 0 };
            auto iter = preSet.begin();
            while (iter != preSet.end()) { // at most 32 elements
                v += *iter;
                curSet.insert(v);
                S.insert(v);
                iter++;
            }
            preSet = curSet;
        }
        return S.size();
    }
};

NOTE:  for above solution, result on VS is correct, while on leetcode, it is wrong.