Scale Engineer

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 ProgrammingBit 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 * 104
  • 0 <= arr[i] <= 109

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.

import java.util.HashSet;import java.util.Set; class Solution {    public int subarrayBitwiseORs(int[] arr) {        Set<Integer> distinctOrs = new HashSet<>();        for (int i = 0; i < arr.length; i++) {            int currentOr = 0;            for (int j = i; j < arr.length; j++) {                currentOr |= arr[j];                distinctOrs.add(currentOr);            }        }        return distinctOrs.size();    }}

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.

Solutions

class Solution {public  int subarrayBitwiseORs(int[] arr) {    Set<Integer> s = new HashSet<>();    s.add(0);    Set<Integer> ans = new HashSet<>();    for (int x : arr) {      Set<Integer> t = new HashSet<>();      for (int y : s) {        t.add(x | y);      }      t.add(x);      s = t;      ans.addAll(s);    }    return ans.size();  }}

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 →

Next problem