Bitwise ORs of Subarrays — Solution in Python, Java & C++
Bitwise ORs of Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Bitwise ORs of Subarrays is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Bit Manipulation
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Compute the bitwise OR of every contiguous non-empty subarray of arr.
Return how many distinct values appear among those results.
Example 1
Input: arr = [0]
Output: 1
Explanation: The only subarray ORs to 0.
Example 2
Input: arr = [1,1,2]
Output: 3
Explanation: The distinct results are 1, 2 and 3.
Example 3
Input: arr = [1,2,4]
Output: 6
Explanation: 1, 2, 3, 4, 6 and 7.
Constraints
1 <= arr.length <= 50000 <= arr[i] <= 1000000000
Hints for Bitwise ORs of Subarrays
Hint 1
Enumerating all subarrays is
O(n²)values — too many at the upper limit.Hint 2
Track the set of ORs of subarrays ending at the current index.
Hint 3
That set stays small — at most about 30 values — because each new element can only add bits.
How to solve Bitwise ORs of Subarrays
Carry forward the set of ORs of subarrays ending at each position. Extending every one of them by the next element, plus the element alone, gives the next position's set — and that set can only be about 30 values wide, because ORs along a fixed right endpoint form a chain that only ever gains bits.
Approach
- Keep
cur, the distinct ORs of subarrays ending at the previous index, starting empty. - For each element
x, build the next set as{x} ∪ {v | x : v in cur}, deduplicated. - Add every value produced to a global result set.
- Return the global set's size.
Why it works
Fixing the right endpoint and extending leftwards produces a non-decreasing chain of ORs, and each strict increase sets at least one new bit — so at most 30 distinct values survive per position. That keeps the total work near O(n · 30) instead of O(n²).
Complexity
- Time —
O(n · 30) - Space —
O(number of distinct ORs)
Pitfalls
- Failing to deduplicate
curlets it grow linearly and the solution degrades toO(n²). - Forgetting the single-element subarray
{x}misses values that no extension produces. - The global set can hold many values; it is
curthat stays small, not the answer.
Reference solution
Python
from typing import List
def subarrayBitwiseORs(arr: List[int]) -> int:
seen = set()
cur = set()
for x in arr:
cur = {x} | {v | x for v in cur}
seen |= cur
return len(seen)Java
public static int subarrayBitwiseORs(int[] arr) {
Set<Integer> seen = new HashSet<>();
Set<Integer> cur = new HashSet<>();
for (int x : arr) {
Set<Integer> next = new HashSet<>();
next.add(x);
for (int v : cur) next.add(v | x);
cur = next;
seen.addAll(cur);
}
return seen.size();
}C++
int subarrayBitwiseORs(vector<int>& arr) {
unordered_set<int> seen, cur;
for (int x : arr) {
unordered_set<int> next;
next.insert(x);
for (int v : cur) next.insert(v | x);
cur = next;
for (int v : cur) seen.insert(v);
}
return (int) seen.size();
}JavaScript
var subarrayBitwiseORs = function(arr) {
var seen = {}, cur = [];
for (var i = 0; i < arr.length; i++) {
var x = arr[i];
var next = [], local = {};
var add = function(v) {
var k = String(v);
if (local[k] !== true) { local[k] = true; next.push(v); }
seen[k] = true;
};
add(x);
for (var j = 0; j < cur.length; j++) add(cur[j] | x);
cur = next;
}
return Object.keys(seen).length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming