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

``````[001]
[001 011] [011]
[001 011 100] [011 100] [100]
[001 011 100 110] [011 100 110] [100 110] [110]
[001 011 100 110 101] [011 100 110 101] [100 110 101] [110 101] [101]
``````

``````001
011 011
111 111 100
111 111 110 110
111 111 111 111 101
``````

``````001
011
111 100
111 110
111 101
``````

``````class Solution {
public:
int subarrayBitwiseORs(vector<int>& A) {
unordered_set<int> res, cur;
for (int i : A) {
unordered_set<int> tmp = {i};
for (int j : cur) tmp.insert(i | j);
cur = tmp;
for (int j : cur) res.insert(j);
}
return res.size();
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/898

https://leetcode.com/problems/bitwise-ors-of-subarrays/

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165859/C%2B%2B-O(kN)-solution

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165881/C%2B%2BJavaPython-O(30N)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation