Watch 10 video solutions for Bitwise ORs of Subarrays, a medium level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by codestorywithMIK has 11,924 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |