Bitwise ORs of Subarrays

Med

#0852Time: `O(n^2)`, where `n` is the length of the array. The two nested loops iterate through all `n * (n + 1) / 2` subarrays, and the operation inside the inner loop is constant time.Space: `O(D)`, where `D` is the number of distinct OR values. In the worst-case scenario, `D` can be on the order of `O(n^2)`, for example, if every subarray produces a unique OR value.1 company

Patterns

Dynamic Programming Bit Manipulation

Data structures

Array

Companies

tcs

Prompt

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 * 10⁴
0 <= arr[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically finds every possible non-empty subarray, calculates its bitwise OR, and counts the number of unique results. A naive implementation would recompute the OR for each subarray from scratch, leading to an O(n^3) complexity. We can optimize this by observing that the OR of a subarray arr[i..j] is simply the OR of arr[i..j-1] and arr[j]. This allows us to compute the ORs for all subarrays starting at a given index i in a single pass, reducing the overall complexity.

Algorithm

1. Initialize an empty HashSet called distinctOrs to store the unique bitwise OR values.
1. Iterate through the input array arr with an index i from 0 to arr.length - 1. This index i will be the starting point of our subarrays.
1. Inside the first loop, initialize an integer currentOr to 0. This will store the bitwise OR of the subarray starting at i.
1. Start a second, nested loop with an index j from i to arr.length - 1. This index j will be the ending point of our subarrays.
1. In the inner loop, update currentOr by performing a bitwise OR with the current element: currentOr |= arr[j].
1. Add the currentOr value to the distinctOrs set. The set will only add the value if it's not already present.
1. After both loops complete, the distinctOrs set contains all unique bitwise ORs of all possible subarrays.
1. Return the size of the distinctOrs set.

Walkthrough

We use two nested loops to iterate through all possible subarrays. The outer loop fixes the starting point i of the subarray, and the inner loop extends the subarray to the right by including elements from j = i to n-1.

A variable currentOr is used to maintain the bitwise OR of the current subarray arr[i..j]. As j increments, we update currentOr by taking the bitwise OR with the new element arr[j]. This avoids recalculating the OR from the beginning of the subarray each time.

All calculated currentOr values are stored in a HashSet to automatically handle uniqueness. The final answer is the size of this set.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int subarrayBitwiseORs(int[] arr) {6        Set<Integer> distinctOrs = new HashSet<>();7        for (int i = 0; i < arr.length; i++) {8            int currentOr = 0;9            for (int j = i; j < arr.length; j++) {10                currentOr |= arr[j];11                distinctOrs.add(currentOr);12            }13        }14        return distinctOrs.size();15    }16}

Complexity

Time

`O(n^2)`, where `n` is the length of the array. The two nested loops iterate through all `n * (n + 1) / 2` subarrays, and the operation inside the inner loop is constant time.

Space

`O(D)`, where `D` is the number of distinct OR values. In the worst-case scenario, `D` can be on the order of `O(n^2)`, for example, if every subarray produces a unique OR value.

Trade-offs

Pros

Simple to understand and implement.
More efficient than the naive O(n^3) approach.

Cons

The O(n^2) time complexity is too slow for the given constraints (n <= 5 * 10^4), leading to a "Time Limit Exceeded" error on larger test cases.

This approach uses a dynamic programming-like strategy combined with a key insight about the bitwise OR operation. We process the array element by element, maintaining a set of all possible OR values for subarrays ending at the current position. The crucial observation is that this set of values is surprisingly small.

Algorithm

1. Initialize a HashSet totalDistinctOrs to store the final unique ORs from all subarrays.
1. Initialize another HashSet currentOrs to store the unique ORs of subarrays ending at the previous element.
1. Iterate through each number num in the input array arr.
1. Inside the loop, create a new temporary HashSet nextOrs. This set will store the unique ORs of subarrays ending at the current element num.
1. Add num itself to nextOrs, as it represents the OR of the subarray containing only num.
1. Iterate through each prevOr value in currentOrs. For each prevOr, calculate prevOr | num and add the result to nextOrs. This computes the ORs for all subarrays ending at the current position that are longer than one element.
1. After the inner loop, nextOrs contains all unique ORs for subarrays ending at num. Update currentOrs to be nextOrs for the next iteration.
1. Add all elements from the new currentOrs to totalDistinctOrs.
1. After iterating through the entire array, return the size of totalDistinctOrs.

Walkthrough

Let R_i be the set of bitwise ORs of all subarrays ending at index i. We can compute R_i based on R_{i-1}: R_i = { x | arr[i] for x in R_{i-1} } U { arr[i] } This means the ORs for subarrays ending at i are either arr[i] itself (for the subarray [arr[i]]) or the result of ORing arr[i] with an OR from a subarray ending at i-1.

The key insight is that the size of R_i is bounded. Consider the sequence of values OR(arr[i..i]), OR(arr[i-1..i]), OR(arr[i-2..i]), ... . This sequence is non-decreasing because a | b >= a. For a value in this sequence to be strictly greater than the previous one, at least one new bit must be set to 1. Since the input numbers are less than or equal to 10^9 (which is less than 2^30), they can be represented by at most 30 bits. Therefore, the number of distinct values in this sequence is at most 30. This implies |R_i| <= 30.

This bound allows for an efficient algorithm. We iterate through the array, and at each step i, we compute R_i from R_{i-1}. Since |R_{i-1}| is small (at most 30), this computation is very fast. We collect all values from all R_i sets into a global set to find the total number of distinct ORs.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int subarrayBitwiseORs(int[] arr) {6        Set<Integer> totalDistinctOrs = new HashSet<>();7        Set<Integer> currentOrs = new HashSet<>();8        9        for (int num : arr) {10            Set<Integer> nextOrs = new HashSet<>();11            nextOrs.add(num);12            for (int prevOr : currentOrs) {13                nextOrs.add(prevOr | num);14            }15            currentOrs = nextOrs;16            totalDistinctOrs.addAll(currentOrs);17        }18        19        return totalDistinctOrs.size();20    }21}

Complexity

Time

`O(n * W)`, where `n` is the length of the array and `W` is the number of bits in the integer type (e.g., 30-32). For each of the `n` elements, we iterate through `currentOrs`. Due to the bitwise OR property, the size of `currentOrs` is bounded by `W`. Thus, the inner loop runs at most `W` times.

Space

`O(n * W)`. The space is dominated by `totalDistinctOrs`. In the worst case, we might add up to `W` new distinct values at each of the `n` steps. The `currentOrs` and `nextOrs` sets require `O(W)` space.

Trade-offs

Pros

Very efficient, easily passing the time constraints.
Leverages a clever property of the bitwise OR operation.

Cons

The reasoning behind the complexity bound is less intuitive than the brute-force approach.
The space complexity, while acceptable, can be larger than the brute-force approach in some average cases, although its worst-case bound is better (O(n*W) vs O(n^2)).

Solutions

Solution

1class Solution {2public3  int subarrayBitwiseORs(int[] arr) {4    Set<Integer> s = new HashSet<>();5    s.add(0);6    Set<Integer> ans = new HashSet<>();7    for (int x : arr) {8      Set<Integer> t = new HashSet<>();9      for (int y : s) {10        t.add(x | y);11      }12      t.add(x);13      s = t;14      ans.addAll(s);15    }16    return ans.size();17  }18}

1class Solution {2public:3  int subarrayBitwiseORs(vector<int> &arr) {4    unordered_set<int> s{{0}};5    unordered_set<int> ans;6    for (int &x : arr) {7      unordered_set<int> t{{x}};8      for (int y : s) {9        t.insert(x | y);10      }11      s = move(t);12      ans.insert(s.begin(), s.end());13    }14    return ans.size();15  }16};

1class Solution:2    def subarrayBitwiseORs(self, arr: List[int]) -> int: s = {0} ans = set() for x in arr: s = {x | y for y in s} | {x} ans |= s return len(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem