# Bitwise ORs of Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bitwise-ors-of-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/bitwise-ors-of-subarrays
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
Given an integer array `arr`, return _the number of distinct bitwise ORs of all the non-empty subarrays of_ `arr`.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A **subarray** is a contiguous non-empty sequence of elements within an array.

**Example 1:**

**Input:** arr = [0]
**Output:** 1
**Explanation:** There is only one possible result: 0.

**Example 2:**

**Input:** arr = [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:** arr = [1,2,4]
**Output:** 6
**Explanation:** The possible results are 1, 2, 3, 4, 6, and 7.

**Constraints:**

* `1 <= arr.length <= 5 * 104`
* `0 <= arr[i] <= 109`

# Approaches
## Brute Force with Optimization
This approach systematically finds every possible non-empty subarray, calculates its bitwise OR, and counts the number of unique results. A naive implementation would recompute the OR for each subarray from scratch, leading to an `O(n^3)` complexity. We can optimize this by observing that the OR of a subarray `arr[i..j]` is simply the OR of `arr[i..j-1]` and `arr[j]`. This allows us to compute the ORs for all subarrays starting at a given index `i` in a single pass, reducing the overall complexity.
**Time:** `O(n^2)`, where `n` is the length of the array. The two nested loops iterate through all `n * (n + 1) / 2` subarrays, and the operation inside the inner loop is constant time. · **Space:** `O(D)`, where `D` is the number of distinct OR values. In the worst-case scenario, `D` can be on the order of `O(n^2)`, for example, if every subarray produces a unique OR value.
**Pros:** Simple to understand and implement.; More efficient than the naive `O(n^3)` approach.
**Cons:** The `O(n^2)` time complexity is too slow for the given constraints (`n <= 5 * 10^4`), leading to a "Time Limit Exceeded" error on larger test cases.
### Explanation
We use two nested loops to iterate through all possible subarrays. The outer loop fixes the starting point `i` of the subarray, and the inner loop extends the subarray to the right by including elements from `j = i` to `n-1`.

A variable `currentOr` is used to maintain the bitwise OR of the current subarray `arr[i..j]`. As `j` increments, we update `currentOr` by taking the bitwise OR with the new element `arr[j]`. This avoids recalculating the OR from the beginning of the subarray each time.

All calculated `currentOr` values are stored in a `HashSet` to automatically handle uniqueness. The final answer is the size of this set.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> distinctOrs = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            int currentOr = 0;
            for (int j = i; j < arr.length; j++) {
                currentOr |= arr[j];
                distinctOrs.add(currentOr);
            }
        }
        return distinctOrs.size();
    }
}
```
### Algorithm
- 1. Initialize an empty `HashSet` called `distinctOrs` to store the unique bitwise OR values.
- 2. Iterate through the input array `arr` with an index `i` from `0` to `arr.length - 1`. This index `i` will be the starting point of our subarrays.
- 3. Inside the first loop, initialize an integer `currentOr` to `0`. This will store the bitwise OR of the subarray starting at `i`.
- 4. Start a second, nested loop with an index `j` from `i` to `arr.length - 1`. This index `j` will be the ending point of our subarrays.
- 5. In the inner loop, update `currentOr` by performing a bitwise OR with the current element: `currentOr |= arr[j]`.
- 6. Add the `currentOr` value to the `distinctOrs` set. The set will only add the value if it's not already present.
- 7. After both loops complete, the `distinctOrs` set contains all unique bitwise ORs of all possible subarrays.
- 8. Return the size of the `distinctOrs` set.

## Dynamic Programming with Bit Manipulation Insight
This approach uses a dynamic programming-like strategy combined with a key insight about the bitwise OR operation. We process the array element by element, maintaining a set of all possible OR values for subarrays ending at the current position. The crucial observation is that this set of values is surprisingly small.
**Time:** `O(n * W)`, where `n` is the length of the array and `W` is the number of bits in the integer type (e.g., 30-32). For each of the `n` elements, we iterate through `currentOrs`. Due to the bitwise OR property, the size of `currentOrs` is bounded by `W`. Thus, the inner loop runs at most `W` times. · **Space:** `O(n * W)`. The space is dominated by `totalDistinctOrs`. In the worst case, we might add up to `W` new distinct values at each of the `n` steps. The `currentOrs` and `nextOrs` sets require `O(W)` space.
**Pros:** Very efficient, easily passing the time constraints.; Leverages a clever property of the bitwise OR operation.
**Cons:** The reasoning behind the complexity bound is less intuitive than the brute-force approach.; The space complexity, while acceptable, can be larger than the brute-force approach in some average cases, although its worst-case bound is better (`O(n*W)` vs `O(n^2)`).
### Explanation
Let `R_i` be the set of bitwise ORs of all subarrays ending at index `i`. We can compute `R_i` based on `R_{i-1}`:
`R_i = { x | arr[i] for x in R_{i-1} } U { arr[i] }`
This means the ORs for subarrays ending at `i` are either `arr[i]` itself (for the subarray `[arr[i]]`) or the result of ORing `arr[i]` with an OR from a subarray ending at `i-1`.

The key insight is that the size of `R_i` is bounded. Consider the sequence of values `OR(arr[i..i])`, `OR(arr[i-1..i])`, `OR(arr[i-2..i])`, ... . This sequence is non-decreasing because `a | b >= a`. For a value in this sequence to be strictly greater than the previous one, at least one new bit must be set to 1. Since the input numbers are less than or equal to `10^9` (which is less than `2^30`), they can be represented by at most 30 bits. Therefore, the number of distinct values in this sequence is at most 30. This implies `|R_i| <= 30`.

This bound allows for an efficient algorithm. We iterate through the array, and at each step `i`, we compute `R_i` from `R_{i-1}`. Since `|R_{i-1}|` is small (at most 30), this computation is very fast. We collect all values from all `R_i` sets into a global set to find the total number of distinct ORs.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> totalDistinctOrs = new HashSet<>();
        Set<Integer> currentOrs = new HashSet<>();
        
        for (int num : arr) {
            Set<Integer> nextOrs = new HashSet<>();
            nextOrs.add(num);
            for (int prevOr : currentOrs) {
                nextOrs.add(prevOr | num);
            }
            currentOrs = nextOrs;
            totalDistinctOrs.addAll(currentOrs);
        }
        
        return totalDistinctOrs.size();
    }
}
```
### Algorithm
- 1. Initialize a `HashSet` `totalDistinctOrs` to store the final unique ORs from all subarrays.
- 2. Initialize another `HashSet` `currentOrs` to store the unique ORs of subarrays ending at the *previous* element.
- 3. Iterate through each number `num` in the input array `arr`.
- 4. Inside the loop, create a new temporary `HashSet` `nextOrs`. This set will store the unique ORs of subarrays ending at the *current* element `num`.
- 5. Add `num` itself to `nextOrs`, as it represents the OR of the subarray containing only `num`.
- 6. Iterate through each `prevOr` value in `currentOrs`. For each `prevOr`, calculate `prevOr | num` and add the result to `nextOrs`. This computes the ORs for all subarrays ending at the current position that are longer than one element.
- 7. After the inner loop, `nextOrs` contains all unique ORs for subarrays ending at `num`. Update `currentOrs` to be `nextOrs` for the next iteration.
- 8. Add all elements from the new `currentOrs` to `totalDistinctOrs`.
- 9. After iterating through the entire array, return the size of `totalDistinctOrs`.

# Solutions
### Java

```java
class Solution {
public
  int subarrayBitwiseORs(int[] arr) {
    Set<Integer> s = new HashSet<>();
    s.add(0);
    Set<Integer> ans = new HashSet<>();
    for (int x : arr) {
      Set<Integer> t = new HashSet<>();
      for (int y : s) {
        t.add(x | y);
      }
      t.add(x);
      s = t;
      ans.addAll(s);
    }
    return ans.size();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int subarrayBitwiseORs(vector<int> &arr) {
    unordered_set<int> s{{0}};
    unordered_set<int> ans;
    for (int &x : arr) {
      unordered_set<int> t{{x}};
      for (int y : s) {
        t.insert(x | y);
      }
      s = move(t);
      ans.insert(s.begin(), s.end());
    }
    return ans.size();
  }
};

```

### Python

```python
class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int: s = {0} ans = set() for x in arr: s = {x | y for y in s} | {x} ans |= s return len(ans)

```