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] <= 109Problem 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.
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.
Python
JavaScript
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.
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.
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.
| 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), factors in the calculation over potentially n subarrays. |
| 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 |
Bitwise ORs of Subarrays | Detailed Explanation | Why Linear Time | Leetcode 898 | codestorywithMIK • codestorywithMIK • 11,924 views views
Watch 9 more video solutions →Practice Bitwise ORs of Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor