> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/subarray-sum/bitwise-ors-of-subarrays.md).

# Bitwise ORs of Subarrays

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

> 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

## Thoughts

不难看出让f\[i]\[j]表示从i到j组成的subarray的值，那么f\[i]\[j+1] = f\[i]\[j] | A\[j+1]. 这么做的时间复杂度是O(N^2)。但其实f\[0]\[j]到f\[j]\[j] 结果并没有j个，而是最多31个。因为f\[i-1]\[j]包含了f\[i]\[j]的位数，只可能在它基础上多几个1，而正整数最多只有31个1。因此用一个]集合保存上次循环(j - 1)得出所有的可能性(最多31个)，与A\[j] 相or即可，时间复杂度从O(N^2)降到了O(31N).

## Code

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

        return res.size();
    }
};
```

## Analysis

时间复杂度O(N). 空间复杂度O(N), 最差情况下cur里每个都是Unique，一共添加了O(N)次.

1. 题目要求是continuous subarray, 漏掉了continuous
2. Continuous subarray的总个数是N^2个，不是指数级个。
3. 结果存在另一个set中。
4. Dp\[i]\[j] (每个I, j往后动以及j, i依次从前到j), 和cur ( the set of results A\[i] | ... | A\[j] for all i., 对每个j, i依次从前到j) 的区别。前者遍历需要O(N), 后者在这道题里是c。