##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/898.html

# 898. Bitwise ORs of Subarrays

Medium

## Description

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: 

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

## Solution

Use a set to store all different bitwise OR results and use a list to store the previous bitwise OR results. For each number in A, add it to the set and the list, and use another list to store the current bitwise OR results. If a bitwise OR result of the current number is greater than the number, then the bitwise OR result is a new result, so add the new result into the second list. After the results of the current number are calculated, assign the second list to the first list. Finally, return the set’s size.

• class Solution {
public int subarrayBitwiseORs(int[] A) {
Set<Integer> totalSet = new HashSet<Integer>();
List<Integer> prevList = new ArrayList<Integer>();
int length = A.length;
for (int i = 0; i < length; i++) {
int num = A[i];
List<Integer> curList = new ArrayList<Integer>();
for (int prevNum : prevList) {
int bitOR = num | prevNum;
if (bitOR > num)
num = bitOR;
}
prevList = new ArrayList<Integer>(curList);
}
}
}

• // OJ: https://leetcode.com/problems/bitwise-ors-of-subarrays/
// Time: O(30N)
// Space: O(30N)
class Solution {
public:
int subarrayBitwiseORs(vector<int>& A) {
unordered_set<int> all, cur, next;
for (int n : A) {
next.clear();
next.insert(n);
for (int prev : cur) next.insert(prev | n);
for (int m : next) all.insert(m);
swap(cur, next);
}
return all.size();
}
};

• class Solution:
def subarrayBitwiseORs(self, arr: List[int]) -> int:
s = set()
prev = 0
for i, v in enumerate(arr):
prev |= v
curr = 0
for j in range(i, -1, -1):
curr |= arr[j]
if curr == prev:
break
return len(s)

############

class Solution(object):
def subarrayBitwiseORs(self, A):
"""
:type A: List[int]
:rtype: int
"""
res = set()
cur = set()
for a in A:
cur = {n | a for n in cur} | {a}
res |= cur
return len(res)

• func subarrayBitwiseORs(arr []int) int {
s := map[int]bool{}
prev := 0
for i, v := range arr {
prev |= v
curr := 0
for j := i; j >= 0; j-- {
curr |= arr[j]
s[curr] = true
if curr == prev {
break
}
}
}
return len(s)
}