> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/bit-manipulation/bitwise-ors-of-subarrays.md).

# 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`

**Explaination:**

For example, an array is \[001, 011, 100, 110, 101] (in binary).

All the subarrays are:

```
[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]
```

In each line, we add a new number to each array of the previous line.

Calculate the OR operations for each subarray:

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

There are O(N^2) numbers in total, which is not acceptable.

After removing duplicate numbers in each line, it becomes:

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

In each line `t`, for any two numbers `t[i]` and `t[j]` (i < j), `t[i]` must have more `1`s than `t[j]`. So the length of each line will not exceed 32. So if we remove duplicate numbers, the complexity would not be very large.

The complexity is O(kN), where k is a constant depends on the bitwise length of input numbers. (32 in this problem)

```java
// We can only increase the number of 1s with |
class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> ans = new HashSet();
        Set<Integer> cur = new HashSet();
        for (int x: arr) {
            Set<Integer> cur2 = new HashSet();
            for (int y: cur)
                cur2.add(x | y);
            cur2.add(x);
            cur = cur2;
            ans.addAll(cur);
        }
        return ans.size();
    }
}
```