> 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();
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/bit-manipulation/bitwise-ors-of-subarrays.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.