# 898. Bitwise ORs of Subarrays

## Description

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

## Solutions

Solution 1: Hash Table

The problem asks for the number of unique bitwise OR operations results of subarrays. If we enumerate the end position $i$ of the subarray, the number of bitwise OR operations results of the subarray ending at $i-1$ does not exceed $32$. This is because the bitwise OR operation is a monotonically increasing operation.

Therefore, we use a hash table $ans$ to record all the results of the bitwise OR operations of subarrays, and a hash table $s$ to record the results of the bitwise OR operations of subarrays ending with the current element. Initially, $s$ only contains one element $0$.

Next, we enumerate the end position $i$ of the subarray. The result of the bitwise OR operation of the subarray ending at $i$ is the set of results of the bitwise OR operation of the subarray ending at $i-1$ and $a[i]$, plus $a[i]$ itself. We use a hash table $t$ to record the results of the bitwise OR operation of the subarray ending at $i$, then we update $s = t$, and add all elements in $t$ to $ans$.

Finally, we return the number of elements in the hash table $ans$.

The time complexity is $O(n \times \log M)$, and the space complexity is $O(n \times \log M)$. Here, $n$ and $M$ are the length of the array and the maximum value in the array, respectively.

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

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

• 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)

• func subarrayBitwiseORs(arr []int) int {
ans := map[int]bool{}
s := map[int]bool{0: true}
for _, x := range arr {
t := map[int]bool{x: true}
for y := range s {
t[x|y] = true
}
s = t
for y := range s {
ans[y] = true
}
}
return len(ans)
}

• function subarrayBitwiseORs(arr: number[]): number {
const s: Set<number> = new Set();
const ans: Set<number> = new Set();
for (const x of arr) {
const t: Set<number> = new Set();
for (const y of s) {
}
s.clear();
for (const y of t) {