LeetCode 898: Bitwise ORs of Subarrays

Problem Restatement

We are given an integer array arr.

For every non-empty contiguous subarray, compute the bitwise OR of all elements in that subarray.

Return the number of distinct OR results.

A subarray must be contiguous. The official constraints allow arr.length <= 5 * 10^4 and arr[i] <= 10^9. (leetcode.com)

Input and Output

Function shape:

def subarrayBitwiseORs(self, arr: list[int]) -> int:
    ...

Examples

Example 1:

Input: arr = [0]
Output: 1

There is only one subarray:

[0]

Its OR result is 0, so there is 1 distinct result.

Example 2:

Input: arr = [1,1,2]
Output: 3

Subarrays and OR values:

Distinct values:

{1, 2, 3}

So the answer is 3.

Example 3:

Input: arr = [1,2,4]
Output: 6

The possible OR results are:

1, 2, 3, 4, 6, 7

So the answer is 6.

First Thought: Check Every Subarray

A direct approach is to enumerate every subarray.

For each start index, extend the end index and keep the running OR.

class Solution:
    def subarrayBitwiseORs(self, arr: list[int]) -> int:
        seen = set()
        n = len(arr)

        for left in range(n):
            value = 0

            for right in range(left, n):
                value |= arr[right]
                seen.add(value)

        return len(seen)

This avoids recomputing the OR from scratch for every subarray, but it still checks O(n^2) subarrays.

With n up to 5 * 10^4, this is too slow.

Key Insight

Instead of tracking all subarrays, track only the OR values of subarrays ending at the current index.

Let:

current = all distinct OR values of subarrays ending at the previous element

When we read a new value x, every subarray ending at x is either:

1. A new subarray containing only x.
2. An old subarray ending at the previous element, extended by x.

So the new set is:

next_current = {x} union {old | x for old in current}

Add every value in next_current to a global set answer.

The reason this is efficient is that bitwise OR only turns bits on. It never turns bits off.

As subarrays get longer, their OR values can change only when a new bit becomes set. Since arr[i] <= 10^9, there are at most about 30 relevant bits. So the number of distinct OR values ending at one position stays small.

Algorithm

Initialize:

all_results = set()
current = set()

For each number x in arr:

1. Build the OR results for subarrays ending at x:

current = {x} | {value | x for value in current}

2. Add these results to the global set:

all_results |= current

Return:

len(all_results)

Walkthrough

Use:

arr = [1, 1, 2]

Start:

current = {}
all_results = {}

Process first 1:

current = {1}
all_results = {1}

Process second 1:

Subarrays ending here:

current = {1}
all_results = {1}

Process 2:

Subarrays ending here:

current = {2, 3}
all_results = {1, 2, 3}

Return:

3

Correctness

At each index, current stores exactly the set of OR results for all subarrays ending at that index.

For the first element, this is true because the only subarray ending there is the single-element subarray.

Assume it is true for the previous index. For the current value x, every subarray ending at the current index is either the single-element subarray [x], or a previous subarray ending at the previous index extended by x.

The OR of [x] is x.

The OR of an extended subarray is the previous OR value OR-ed with x.

Therefore:

{x} union {old | x for old in previous_current}

contains exactly all OR values of subarrays ending at the current index.

The algorithm adds every current set into all_results, so all_results contains exactly the OR values of all non-empty subarrays.

Thus, returning the size of all_results gives the required number of distinct bitwise OR results.

Complexity

Let:

n = len(arr)
B = number of bits needed to represent max(arr)

For the given constraints, B is at most about 30.

Implementation

class Solution:
    def subarrayBitwiseORs(self, arr: list[int]) -> int:
        all_results = set()
        current = set()

        for x in arr:
            current = {x | value for value in current}
            current.add(x)

            all_results |= current

        return len(all_results)

Code Explanation

current stores OR values for subarrays ending at the previous index:

current = set()

all_results stores every OR value seen so far:

all_results = set()

For each value x, we extend every previous ending subarray:

current = {x | value for value in current}

Then we also include the new single-element subarray:

current.add(x)

Now current contains all OR values for subarrays ending at this position.

We merge them into the global result set:

all_results |= current

At the end, the answer is the number of distinct OR values:

return len(all_results)

Testing

def run_tests():
    s = Solution()

    assert s.subarrayBitwiseORs([0]) == 1
    assert s.subarrayBitwiseORs([1, 1, 2]) == 3
    assert s.subarrayBitwiseORs([1, 2, 4]) == 6
    assert s.subarrayBitwiseORs([7, 7, 7]) == 1
    assert s.subarrayBitwiseORs([0, 1, 2]) == 4
    assert s.subarrayBitwiseORs([3, 1, 5]) == 5

    print("all tests passed")

run_tests()

Test meaning: