Problem Description

Given an integer array arr, you need to find the total number of distinct bitwise OR results that can be obtained from all possible non-empty subarrays.

A subarray is a contiguous sequence of elements from the array. For example, if arr = [1, 2, 3], the subarrays are: [1], [2], [3], [1,2], [2,3], and [1,2,3].

For each subarray, calculate the bitwise OR of all its elements:

• If the subarray has only one element, the bitwise OR is just that element itself
• If the subarray has multiple elements, apply the bitwise OR operation across all elements

Your task is to count how many unique values you can get from performing this operation on all possible subarrays.

For example, if arr = [1, 2]:

• Subarray [1] gives bitwise OR = 1
• Subarray [2] gives bitwise OR = 2
• Subarray [1, 2] gives bitwise OR = 1 | 2 = 3
• The distinct values are {1, 2, 3}, so the answer is 3

The solution uses a rolling set approach where for each position i, it maintains the set of all possible OR values for subarrays ending at position i. This works efficiently because the number of distinct OR values ending at any position is bounded by the number of bits (at most 32 for integers), making the algorithm practical despite the potentially large number of subarrays.

Intuition

The key insight is understanding how the bitwise OR operation behaves when we extend subarrays. The OR operation has a special property: it can only turn bits from 0 to 1, never from 1 to 0. This means as we extend a subarray by adding more elements, the OR result either stays the same or increases.

Consider what happens when we process each element in the array sequentially. At position i, we want to know all possible OR values for subarrays ending at this position. These subarrays can be:

1. Just the element itself: [arr[i]]
2. Element combined with previous subarrays: [arr[j], ..., arr[i]] for all valid j < i

Here's the crucial observation: when we move from position i-1 to position i, each subarray ending at i-1 can be extended by including arr[i]. If we had a subarray with OR value y ending at position i-1, extending it gives us y | arr[i] ending at position i.

But why doesn't this explode into too many values? Because of the monotonic property of OR - once a bit is set to 1, it stays 1. For a 32-bit integer, there are at most 32 bits that can change from 0 to 1. This means at any position, we can have at most 32 distinct OR values for subarrays ending there, regardless of how long the array is.

This leads to our approach: maintain a set s of all distinct OR values for subarrays ending at the current position. When we move to the next element x, the new set becomes:

• All previous values OR'd with x: {y | x for y in s}
• Plus x itself (for the subarray containing just x)

By collecting all these intermediate sets into a global set ans, we capture all distinct OR values across all possible subarrays in the array.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation uses a hash table-based approach to efficiently track all distinct bitwise OR values.

Data Structures:

• ans: A set that stores all unique bitwise OR values found across all subarrays
• s: A set that maintains the distinct OR values for all subarrays ending at the current position

Algorithm Steps:

1. Initialize the result set: Create an empty set ans to collect all distinct OR values throughout the process.

2. Initialize the current set: Create an empty set s that will track OR values for subarrays ending at the current position.

3. Process each element: For each element x in the array:

   a. Generate new OR values: Create a new set containing:

   • {x | y for y in s}: All previous OR values combined with the current element
   • {x}: The current element itself (representing a subarray of length 1)

   b. Update the current set: Replace s with this new set of OR values

   c. Collect results: Add all values from s to the global ans set using the union operation ans |= s

4. Return the count: The size of ans gives us the total number of distinct bitwise OR values.

Why this works efficiently:

The key optimization is that at each position i, the set s contains at most 32 elements (for 32-bit integers). This is because:

• Each OR value in s represents a different bit pattern
• As we extend subarrays with OR operations, bits can only change from 0 to 1
• Once all 32 bits are set to 1, no further changes are possible
• Therefore, we can have at most 32 distinct transitions/values

Time Complexity: O(n × 32) = O(n) where n is the length of the array, since we process each element once and maintain at most 32 values per position.

Space Complexity: O(32 × n) = O(n) in the worst case for storing all distinct OR values across all positions.

Example Walkthrough

Let's walk through the solution with arr = [1, 1, 2] to see how the rolling set approach works.

Binary representations:

• 1 = 001
• 2 = 010

Step-by-step process:

Initial state:

• ans = {} (global set for all distinct OR values)
• s = {} (set for OR values ending at current position)

Processing arr[0] = 1:

• Generate new set: {y | 1 for y in {}} ∪ {1} = {1}
• Update s = {1}
• Update ans = ans ∪ s = {1}
• This represents subarray [1] with OR value 1

Processing arr[1] = 1:

• Previous s = {1}
• Generate new set: {y | 1 for y in {1}} ∪ {1} = {1 | 1} ∪ {1} = {1} ∪ {1} = {1}
• Update s = {1}
• Update ans = ans ∪ s = {1} ∪ {1} = {1}
• This represents subarrays [1] and [1,1], both with OR value 1

Processing arr[2] = 2:

• Previous s = {1}
• Generate new set: {y | 2 for y in {1}} ∪ {2} = {1 | 2} ∪ {2} = {3} ∪ {2} = {2, 3}
• Update s = {2, 3}
• Update ans = ans ∪ s = {1} ∪ {2, 3} = {1, 2, 3}
• This represents:
  • Subarray [2] with OR value 2
  • Subarray [1,2] with OR value 3 (from extending [1])
  • Subarray [1,1,2] with OR value 3 (from extending [1,1])

Final result:

• ans = {1, 2, 3}
• Count = 3

Verification of all subarrays:

• [1] → 1
• [1,1] → 1 | 1 = 1
• [1,1,2] → 1 | 1 | 2 = 3
• [1] (second one) → 1
• [1,2] → 1 | 2 = 3
• [2] → 2

Distinct values: {1, 2, 3}, confirming our answer of 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M)

The key insight is that for each position i, the set s contains all possible OR values of subarrays ending at position i. When we compute {x | y for y in s} for a new element x, the size of set s is bounded by O(log M) where M is the maximum value in the array.

This bound exists because:

• The bitwise OR operation can only set bits to 1, never to 0
• Each distinct value in s must differ by at least one bit position
• Since there are at most log M bit positions in a number with maximum value M, there can be at most O(log M) distinct OR values for subarrays ending at any position

Therefore, for each of the n elements, we perform O(log M) OR operations, resulting in O(n × log M) time complexity.

Space Complexity: O(n × log M)

The space is dominated by the ans set, which stores all distinct OR values across all subarrays. In the worst case:

• For each of the n positions, we can have up to O(log M) distinct OR values for subarrays ending at that position
• The total number of distinct OR values across all subarrays is bounded by O(n × log M)

The temporary set s uses O(log M) space at any given time, which doesn't affect the overall complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Brute Force Approach Without Optimization

The Pitfall: Many developers initially attempt to solve this problem by generating all possible subarrays explicitly and calculating their bitwise OR values:

# INEFFICIENT APPROACH - Don't use this!
def subarrayBitwiseORs_bruteforce(arr):
    results = set()
    n = len(arr)
    for i in range(n):
        for j in range(i, n):
            or_value = 0
            for k in range(i, j + 1):
                or_value |= arr[k]
            results.add(or_value)
    return len(results)

Why it's problematic:

• Time complexity: O(n³) - triple nested loops make it extremely slow for large inputs
• Will cause Time Limit Exceeded (TLE) on LeetCode for arrays with thousands of elements
• Doesn't leverage the mathematical properties of bitwise OR operations

The Solution: Use the rolling set approach that maintains only distinct OR values ending at each position, reducing complexity to O(32n).

2. Not Resetting the Current Set Correctly

The Pitfall: Incorrectly updating the current_ending_here set by modifying it in place:

# INCORRECT - Modifies set while iterating
for num in arr:
    for prev_value in current_ending_here:  # Dangerous!
        current_ending_here.add(num | prev_value)
    current_ending_here.add(num)

Why it's problematic:

• Modifying a set while iterating over it can cause runtime errors or unexpected behavior
• May miss some values or process others multiple times
• Can lead to infinite loops in some programming languages

The Solution: Create a new set for each iteration:

current_ending_here = {num | prev_value for prev_value in current_ending_here} | {num}

3. Forgetting to Include Single-Element Subarrays

The Pitfall: Only considering OR operations between multiple elements:

# INCORRECT - Missing single elements
for num in arr:
    current_ending_here = {num | prev_value for prev_value in current_ending_here}
    # Forgot to add {num} itself!

Why it's problematic:

• Single-element subarrays are valid subarrays
• Missing these will give incorrect counts
• For example, [5] has one subarray [5] with OR value 5, which must be counted

The Solution: Always include the current element as a standalone subarray:

current_ending_here = {num | prev_value for prev_value in current_ending_here} | {num}

4. Not Understanding Why the Algorithm is Efficient

The Pitfall: Worrying that maintaining sets for each position might still be O(n²) space/time:

# Concern: "Won't this still be inefficient if current_ending_here grows large?"

Why it's not a problem: The key insight is that current_ending_here can contain at most 32 distinct values (for 32-bit integers) because:

• Bitwise OR can only turn bits from 0 to 1, never from 1 to 0
• Once a bit is set in any subarray ending at position i, it remains set in all longer subarrays ending at positions > i
• This creates at most 32 distinct bit patterns (one for each bit position)

The Solution: Trust the mathematical bound - the set size is naturally limited by the bit width of integers, making the algorithm efficient despite processing all subarrays conceptually.