# LeetCode 898: Bitwise ORs of Subarrays

## Problem Restatement

We are given an integer array `arr`.

For every non-empty contiguous subarray, compute the bitwise OR of all elements in that subarray.

Return the number of distinct OR results.

A subarray must be contiguous. The official constraints allow `arr.length <= 5 * 10^4` and `arr[i] <= 10^9`. ([leetcode.com](https://leetcode.com/problems/bitwise-ors-of-subarrays/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | `arr`, an integer array |
| Output | Number of distinct bitwise OR results |
| Subarray | Contiguous non-empty segment |
| Operation | Bitwise OR over all values in the subarray |

Function shape:

```python
def subarrayBitwiseORs(self, arr: list[int]) -> int:
    ...
```

## Examples

Example 1:

```text
Input: arr = [0]
Output: 1
```

There is only one subarray:

```text
[0]
```

Its OR result is `0`, so there is `1` distinct result.

Example 2:

```text
Input: arr = [1,1,2]
Output: 3
```

Subarrays and OR values:

| Subarray | OR |
|---|---:|
| `[1]` | 1 |
| `[1]` | 1 |
| `[2]` | 2 |
| `[1,1]` | 1 |
| `[1,2]` | 3 |
| `[1,1,2]` | 3 |

Distinct values:

```text
{1, 2, 3}
```

So the answer is `3`.

Example 3:

```text
Input: arr = [1,2,4]
Output: 6
```

The possible OR results are:

```text
1, 2, 3, 4, 6, 7
```

So the answer is `6`.

## First Thought: Check Every Subarray

A direct approach is to enumerate every subarray.

For each start index, extend the end index and keep the running OR.

```python
class Solution:
    def subarrayBitwiseORs(self, arr: list[int]) -> int:
        seen = set()
        n = len(arr)

        for left in range(n):
            value = 0

            for right in range(left, n):
                value |= arr[right]
                seen.add(value)

        return len(seen)
```

This avoids recomputing the OR from scratch for every subarray, but it still checks `O(n^2)` subarrays.

With `n` up to `5 * 10^4`, this is too slow.

## Key Insight

Instead of tracking all subarrays, track only the OR values of subarrays ending at the current index.

Let:

```text
current = all distinct OR values of subarrays ending at the previous element
```

When we read a new value `x`, every subarray ending at `x` is either:

1. A new subarray containing only `x`.
2. An old subarray ending at the previous element, extended by `x`.

So the new set is:

```python
next_current = {x} union {old | x for old in current}
```

Add every value in `next_current` to a global set `answer`.

The reason this is efficient is that bitwise OR only turns bits on. It never turns bits off.

As subarrays get longer, their OR values can change only when a new bit becomes set. Since `arr[i] <= 10^9`, there are at most about 30 relevant bits. So the number of distinct OR values ending at one position stays small.

## Algorithm

Initialize:

```python
all_results = set()
current = set()
```

For each number `x` in `arr`:

1. Build the OR results for subarrays ending at `x`:

```python
current = {x} | {value | x for value in current}
```

2. Add these results to the global set:

```python
all_results |= current
```

Return:

```python
len(all_results)
```

## Walkthrough

Use:

```text
arr = [1, 1, 2]
```

Start:

```text
current = {}
all_results = {}
```

Process first `1`:

```text
current = {1}
all_results = {1}
```

Process second `1`:

Subarrays ending here:

| Subarray | OR |
|---|---:|
| `[1]` | 1 |
| `[1,1]` | 1 |

```text
current = {1}
all_results = {1}
```

Process `2`:

Subarrays ending here:

| Subarray | OR |
|---|---:|
| `[2]` | 2 |
| `[1,2]` | 3 |
| `[1,1,2]` | 3 |

```text
current = {2, 3}
all_results = {1, 2, 3}
```

Return:

```python
3
```

## Correctness

At each index, `current` stores exactly the set of OR results for all subarrays ending at that index.

For the first element, this is true because the only subarray ending there is the single-element subarray.

Assume it is true for the previous index. For the current value `x`, every subarray ending at the current index is either the single-element subarray `[x]`, or a previous subarray ending at the previous index extended by `x`.

The OR of `[x]` is `x`.

The OR of an extended subarray is the previous OR value OR-ed with `x`.

Therefore:

```text
{x} union {old | x for old in previous_current}
```

contains exactly all OR values of subarrays ending at the current index.

The algorithm adds every `current` set into `all_results`, so `all_results` contains exactly the OR values of all non-empty subarrays.

Thus, returning the size of `all_results` gives the required number of distinct bitwise OR results.

## Complexity

Let:

```text
n = len(arr)
B = number of bits needed to represent max(arr)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * B)` | Each `current` set has at most `O(B)` distinct OR values |
| Space | `O(n * B)` | The global result set may store many distinct results |

For the given constraints, `B` is at most about `30`.

## Implementation

```python
class Solution:
    def subarrayBitwiseORs(self, arr: list[int]) -> int:
        all_results = set()
        current = set()

        for x in arr:
            current = {x | value for value in current}
            current.add(x)

            all_results |= current

        return len(all_results)
```

## Code Explanation

`current` stores OR values for subarrays ending at the previous index:

```python
current = set()
```

`all_results` stores every OR value seen so far:

```python
all_results = set()
```

For each value `x`, we extend every previous ending subarray:

```python
current = {x | value for value in current}
```

Then we also include the new single-element subarray:

```python
current.add(x)
```

Now `current` contains all OR values for subarrays ending at this position.

We merge them into the global result set:

```python
all_results |= current
```

At the end, the answer is the number of distinct OR values:

```python
return len(all_results)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.subarrayBitwiseORs([0]) == 1
    assert s.subarrayBitwiseORs([1, 1, 2]) == 3
    assert s.subarrayBitwiseORs([1, 2, 4]) == 6
    assert s.subarrayBitwiseORs([7, 7, 7]) == 1
    assert s.subarrayBitwiseORs([0, 1, 2]) == 4
    assert s.subarrayBitwiseORs([3, 1, 5]) == 5

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[0]` | Minimum case |
| `[1,1,2]` | Duplicate OR results |
| `[1,2,4]` | Produces many distinct ORs |
| `[7,7,7]` | All ORs collapse to one value |
| `[0,1,2]` | Includes zero |
| `[3,1,5]` | Mixed overlapping bit patterns |