Skip to main content
Talentd

Bitwise ORs of Subarrays - Solution & Explanation

MediumArrayDynamic ProgrammingBit Manipulation13 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

In the C++ solution, we use unordered sets to track subarray OR values efficiently. For each element, new OR values are calculated by combining with values in current. This results in minimal duplication and improved handling of unique OR results.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n^2), factors in the calculation over potentially n subarrays.
Space Complexity: O(n) based on storage requirements of processed subarrays into result sets.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), for storing the OR results in sets.

Iterative Subarray Expansion

Time Complexity: O(n^2), factors in the calculation over potentially n subarrays.
Space Complexity: O(n) based on storage requirements of processed subarrays into result sets.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray ORO(n²)O(n²)Useful for understanding the problem or when input size is very small
Dynamic Expansion of SubarraysO(n log V)O(log V)General optimal solution; tracks OR states ending at each index
Iterative Subarray ExpansionO(n log V)O(log V)Preferred implementation in C++/Java with explicit state iteration

Video Solution

Bitwise ORs of Subarrays | Detailed Explanation | Why Linear Time | Leetcode 898 | codestorywithMIK • codestorywithMIK • 12,412 views views

Watch 9 more video solutions →

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

Ready to solve this problem?

Practice Bitwise ORs of Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bitwise OR of All Subsequence Sums

Next

Find the Maximum Sequence Value of Array