898. Bitwise ORs of Subarrays

898. Bitwise ORs of Subarrays (Medium)

We have an array arr of non-negative integers.

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

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

 

Example 1:

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

Example 2:

Input: arr = [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: arr = [1,2,4]
Output: 6
Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 109

Companies:
Amazon

Related Topics:
Array, Dynamic Programming, Bit Manipulation

Solution 1.

Complexity Analysis:

Let XOR(i, j) = A[i] | A[i + 1] | ... | A[j]. Hash set cur stores all XOR(0, i), XOR(1, i), ..., XOR(i, i).

Since

• there are at most 30 bits for a positive number 0 <= A[i] <= 1e9
• XOR(k, i) must covers all the bits in XOR(k + 1, i) and at most has one more bit 1 than the latter.

The set cur or the sequence XOR(0, i), XOR(1, i), ..., XOR(i, i) must at most has 30 unique values.

So, cur.size() <= 30 and ans.size() <= 30 * A.size().

So the time and space complexities are O(30N).

// OJ: https://leetcode.com/problems/bitwise-ors-of-subarrays/
// Author: github.com/lzl124631x
// Time: O(30N)
// Space: O(30N)
class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set<int> all, cur, next;
        for (int n : A) {
            next.clear();
            next.insert(n);
            for (int prev : cur) next.insert(prev | n);
            for (int m : next) all.insert(m);
            swap(cur, next);
        }
        return all.size();
    }
};

Or use vector<int>.

// OJ: https://leetcode.com/problems/bitwise-ors-of-subarrays/
// Author: github.com/lzl124631x
// Time: O(30N)
// Space: O(30N)
class Solution {
public:
    int subarrayBitwiseORs(vector<int> A) {
        vector<int> ans;
        int left = 0, right; // numbers in range [left, right) correspond to `cur` set.
        for (int n : A) {
            right = ans.size();
            ans.push_back(n);
            for (int i = left; i < right; ++i) {
                if (ans.back() != (ans[i] | n)) {
                    ans.push_back(ans[i] | n);
                }
            }
            left = right;
        }
        sort(begin(ans), end(ans));
        return unique(begin(ans), end(ans)) - begin(ans);
    }
};