Bitwise ORs of Subarrays
Problem
Given an integer array arr, take the bitwise OR of every contiguous subarray. Return the number of distinct values among all those subarray ORs.
arr = [1, 1, 2]3def subarray_bitwise_ors(arr):
result = set()
cur = set()
for x in arr:
cur = {x | y for y in cur} | {x}
result |= cur
return len(result)function subarrayBitwiseORs(arr) {
const result = new Set();
let cur = new Set();
for (const x of arr) {
const next = new Set([x]);
for (const y of cur) next.add(x | y);
cur = next;
for (const v of cur) result.add(v);
}
return result.size;
}class Solution {
public int subarrayBitwiseORs(int[] arr) {
Set<Integer> result = new HashSet<>();
Set<Integer> cur = new HashSet<>();
for (int x : arr) {
Set<Integer> next = new HashSet<>();
next.add(x);
for (int y : cur) next.add(x | y);
cur = next;
result.addAll(cur);
}
return result.size();
}
}int subarrayBitwiseORs(vector<int>& arr) {
unordered_set<int> result, cur;
for (int x : arr) {
unordered_set<int> next;
next.insert(x);
for (int y : cur) next.insert(x | y);
cur = next;
result.insert(cur.begin(), cur.end());
}
return (int)result.size();
}Explanation
We need to count how many distinct OR values appear across all contiguous subarrays. There are about n² subarrays, so computing each OR from scratch would be slow. The trick is a rolling set that builds new results from old ones.
The key idea: let cur be the set of OR values of all subarrays that end at the current index. When we move to the next element x, every subarray ending here is either just x alone, or an earlier subarray extended by x — which means OR-ing x into each old value.
So each step computes cur = {x | y for y in cur} ∪ {x}, then folds everything in cur into a global result set. Using sets automatically removes duplicates.
This stays fast because OR only ever turns bits on, so as you extend a subarray the value can only grow, and cur never holds more than about 32 distinct values (one per bit). The final answer is the size of result.
Example: arr = [1, 1, 2]. The subarray ORs are 1, 1, 2, 1, 3, 3; the distinct set is {1, 2, 3}, so the answer is 3.