LeetCode: 898. Bitwise ORs of Subarrays

题目描述

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 <= A.length <= 50000
0 <= A[i] <= 10^9

解题思路

A[x...i], x = 0...1 的 Bitwise ORs 是 A[x...i-1], x=0...i-1 的 Bitwise ORs 异或 A[i]。

AC 代码

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        set<int> record;
        set<int> ans;

        for(int i = 0; i < A.size(); ++i)
        {
            set<int> cur;
            // A[x...i] x = 0...i 的所有可能 
            for(int x : record) cur.insert(x | A[i]);
            cur.insert(A[i]);
            record = cur;

            ans.insert(cur.begin(), cur.end());
        }

        return ans.size();
    }
};