Bitwise ORs of Subarrays solution and explanation
TCS
Google
9 more videos on this problem
Bitwise ORs of Subarrays | Detailed Explanation | Why Linear Time | Leetcode 898 | codestorywithMIKcodestorywithMIK · 25:59 · 12K views
Bitwise ORs of Subarrays | Leetcode 898 | DP + Bit ManipulationTechdose · 25:09 · 3K views
898. Bitwise ORs of Subarrays | Leetcode Daily - PythonLeetcode Daily · 7:49 · 1K views
Daily Leetcode #1948: Jul 31, 2025 - 898. Bitwise ORs of SubarraysProgramming Live with Larry · 21:57 · 802 views
898. Bitwise ORs of Subarrays | Leetcode Daily Challenge | Bit Manipulation | Sets | DPEye on AI and DSA · 15:11 · 774 views
Leetcode 898 🔥 Bitwise ORs of Subarrays | Java Set + Prefix OR | Today’s DCC Handwritten Study Placement · 9:13 · 536 views
Leetcode 898. Bitwise ORs of Subarrays | Explained with Python Code & IntuitionStatLearn Tech · 14:41 · 499 views
Bitwise ORs of Subarrays | LeetCode 898 | Java Code | Developer CoderDeveloper Coder · 20:00 · 172 views
Bitwise ORs of Subarrays | LeetCode 898 | Bit ManipulationcodeTips · 10:11 · 145 views
Bitwise ORs of Subarrays | LeetCode 898 - Pythonimpoldev · 9:59 · 108 views
The 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 * 1040 <= arr[i] <= 109
Approach overview
Problem Overview: Given an integer array, compute the number of distinct values produced by taking the bitwise OR of every possible subarray. Each subarray contributes a value, but duplicates count only once. The challenge is avoiding the obvious O(n²) enumeration of all subarrays.
Approach 1: Brute Force Subarray OR (O(n²) time, O(n²) space)
Generate every subarray using two nested loops. For each starting index, extend the subarray to the right and keep updating the OR value using current |= arr[j]. Insert each result into a hash set to track unique values. This approach is straightforward and demonstrates the definition of the problem clearly. However, the number of subarrays is O(n²), so it becomes slow for large inputs.
Approach 2: Dynamic Expansion of Subarrays (O(n log V) time, O(log V) space)
Track all distinct OR values of subarrays that end at the current index. For each element x, take the previous set of OR results and compute prev_or | x. Add these values plus x itself into a new set. The key insight: OR values can only gain bits, so the number of distinct states per index is bounded by the number of bits (≈32 for integers). Maintain a global set for all results seen so far. This reduces the number of operations dramatically compared with brute force and works well with bit manipulation and incremental dynamic programming ideas.
Approach 3: Iterative Subarray Expansion (O(n log V) time, O(log V) space)
This implementation follows the same insight but emphasizes iterative propagation of OR states. Maintain a container of OR results from the previous step. For the next element, iterate through that container and compute updated OR values, inserting them into a new container while deduplicating. Merge the results into a global set of answers. Because OR values stabilize quickly as bits accumulate, the state size remains small. This pattern appears frequently in array problems that involve monotonic bitwise growth.
Recommended for interviews: Start by explaining the brute force idea to show understanding of subarray enumeration. Then move to the dynamic expansion approach. Interviewers typically expect the O(n log V) solution because it leverages the monotonic nature of bitwise OR and demonstrates strong insight into state compression.
Approach 1: Dynamic Expansion of Subarrays
In this approach, we maintain two sets: current and result. current contains the cumulative bitwise ORs of subarrays ending at the current index, while result helps track all distinct OR values found so far. For each element, we extend the subarrays by ORing them with the current element, thus updating their values in current. We also add the direct OR value of the single element subarray.
def subarrayBitwiseORs(arr):
result = set()
current = set()
for x in arr:
current = {x | y for y in current} | {x}
result |= current
return len(result)function subarrayBitwiseORs(arr) {
let result = new Set();
let current = new Set();
for (let x of arr) {
let newCurrent = new Set([x]);
for (let y of current) {
newCurrent.add(x | y);
}
current = newCurrent;
for (let n of current) {
result.add(n);
}
}
return result.size;
}In the Python solution, we initialize the result set to collect distinct OR values, and current set to track the ORs for subarrays ending at each position in the array. With each element x, we compute new OR values by ORing x with each value in current, adding the OR of x as a subarray on its own. This approach efficiently updates and maintains the distinct OR results.
Time Complexity: O(n^2), where n is the length of the array. Each element causes us to evaluate prior OR results.
Space Complexity: O(n), for storing the OR results in sets.
Approach 2: Iterative Subarray Expansion
This approach iteratively considers every ending element of the array, builds valid subarrays up to that point, and accumulates OR results. By systematically building upon already computed OR results, we efficiently form and track new subarrays without backtracking.
import java.util.HashSet;
import java.util.Set;
public class Solution {
public int subarrayBitwiseORs(int[] arr) {
Set<Integer> result = new HashSet<>();
Set<Integer> current = new HashSet<>();
for (int x : arr) {
Set<Integer> newCurrent = new HashSet<>();
newCurrent.add(x);
for (int y : current) {
newCurrent.add(x | y);
}
current = newCurrent;
result.addAll(current);
}
return result.size();
}
}#include <vector>
#include <unordered_set>
using namespace std;
int subarrayBitwiseORs(vector<int>& arr) {
unordered_set<int> result;
unordered_set<int> current;
for (int x : arr) {
unordered_set<int> newCurrent = {x};
for (int y : current) {
newCurrent.insert(x | y);
}
current = newCurrent;
result.insert(current.begin(), current.end());
}
return result.size();
}Java's solution employs HashSet to manage unique OR values efficiently. It processes each array element, updating subarrays' OR values with both immediate and cumulative results. The use of HashSet ensures no duplicate work, storing distinct results throughout the traversal.
Time Complexity: O(n^2), whereby each element's OR value calculation includes both previous and current set components.
Space Complexity: O(n), driven by aggregate set storage needs.
Approach 3: 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.
function subarrayBitwiseORs(arr: number[]): number {
const ans: Set<number> = new Set();
const s: Set<number> = new Set();
for (const x of arr) {
const t: Set<number> = new Set([x]);
for (const y of s) {
t.add(x | y);
}
s.clear();
for (const y of t) {
ans.add(y);
s.add(y);
}
}
return ans.size;
}func subarrayBitwiseORs(arr []int) int {
ans := map[int]bool{}
s := map[int]bool{}
for _, x := range arr {
t := map[int]bool{x: true}
for y := range s {
t[x|y] = true
}
for y := range t {
ans[y] = true
}
s = t
}
return len(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Expansion of Subarrays | Time Complexity: O(n^2), where n is the length of the array. Each element causes us to evaluate prior OR results. |
| Iterative Subarray Expansion | Time Complexity: O(n^2), whereby each element's OR value calculation includes both previous and current set components. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray OR | O(n²) | O(n²) | Useful for understanding the problem or when input size is very small |
| Dynamic Expansion of Subarrays | O(n log V) | O(log V) | General optimal solution; tracks OR states ending at each index |
| Iterative Subarray Expansion | O(n log V) | O(log V) | Preferred implementation in C++/Java with explicit state iteration |
Frequently asked questions
Is Bitwise ORs of Subarrays easy or hard?
The problem is rated Medium on LeetCode. The brute force idea is simple, but recognizing that OR results grow monotonically and can be compressed into a small set of states requires deeper insight into bit manipulation and dynamic programming patterns.
Bitwise ORs of Subarrays Python/Java solution
Python implementations typically use a set to store OR states and update them with set comprehensions or loops. Java solutions use HashSet while iterating through previous states to compute new OR values. The algorithm remains the same across Python, Java, C++, and JavaScript.
How to solve Bitwise ORs of Subarrays in O(n)?
A strict O(n) solution is difficult because each step may produce several new OR states. However, the dynamic expansion technique effectively behaves close to linear since the number of unique OR values per index is limited by the bit count of integers (around 30–32). This yields O(n log V) complexity in practice.
What is the best approach for Bitwise ORs of Subarrays?
The optimal approach tracks all distinct bitwise OR values of subarrays ending at each index. For every new element, combine it with previously computed OR states and store the results in a set. Because OR operations only add bits, the number of states stays small (bounded by the bit width). This gives about O(n log V) time complexity.
Is Bitwise ORs of Subarrays asked at Google/Amazon/Meta?
Bit manipulation and subarray aggregation problems like this appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of bitwise properties, state compression, and efficient subarray processing.
What data structure is used in Bitwise ORs of Subarrays?
A hash set (or unordered set) is used to store distinct OR values. One set tracks OR values of subarrays ending at the current index, and another global set collects all unique results. Arrays and bitwise operators drive the main computation.
What is the time complexity of Bitwise ORs of Subarrays?
The optimized solution runs in O(n log V) time where V is the maximum value in the array (typically up to 32 bits). Each index keeps a small set of OR states because bits only accumulate and cannot be removed. Space complexity is also O(log V).