#898

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Bitwise ORs of Subarrays

Compute the number of unique bitwise OR values from all non-empty subarrays using dynamic state transitions efficiently.

array dynamic programming bit manipulation

Problem Statement

Given an integer array arr, calculate the number of distinct results generated by performing a bitwise OR on every non-empty contiguous subarray of arr. Each subarray contributes one OR value obtained from combining its elements.

For example, in an array [1,2,4], compute the OR for subarrays like [1], [1,2], [2,4], and so on. Return the total count of unique OR results across all these subarrays. This requires careful tracking of intermediate OR values to avoid redundant calculations.

Examples

Example 1

Input: arr = [0]

Output: 1

There is only one possible result: 0.

Example 2

Input: arr = [1,1,2]

Output: 3

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

The possible results are 1, 2, 3, 4, 6, and 7.

Constraints

1 <= arr.length <= 5 * 104
0 <= arr[i] <= 109

Solution Approach

Track Current Subarray ORs

Maintain a set of OR values for all subarrays ending at the current index. For each element, compute new OR values by OR-ing it with every value in the previous set of OR results. Add the current element itself as a singleton subarray.

Aggregate Unique Results

Use a global set to store all distinct OR values encountered. After processing each element, merge the current set into the global set to ensure duplicates across different subarrays are counted only once.

Iterate Efficiently with DP

Leverage the fact that OR values are monotonic in terms of bits: OR-ing more elements never reduces bits. This allows you to only keep the ORs from the previous step and avoid storing all subarrays explicitly, keeping space and time manageable.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * k) where n is array length and k is the number of unique OR values per step, which is bounded by 32 bits. Space complexity is O(k) for the sets storing intermediate and global ORs.

What Interviewers Usually Probe

Ask about the maximum size of the input array and integer limits to assess time/space concerns.
Check if the candidate can identify that storing all subarrays explicitly is inefficient.
Probe understanding of bitwise properties and how OR operations accumulate distinct values.

Common Pitfalls or Variants

Common pitfalls

Attempting to store all subarrays explicitly, which exceeds memory limits.
Failing to merge OR results correctly, leading to duplicate counts in the final answer.
Not recognizing that the number of distinct ORs is limited by the number of bits, not array size.

Follow-up variants

Count distinct bitwise ANDs of all subarrays instead of ORs, requiring reverse bit propagation.
Return the sum of all distinct ORs of subarrays rather than the count.
Limit subarray length to k and compute distinct ORs only within these constrained windows.

FAQ

What is the key pattern to solve Bitwise ORs of Subarrays efficiently?

The problem follows a state transition dynamic programming pattern where you track OR values of subarrays ending at each index, avoiding storing all subarrays.

Can I solve this problem using brute force?

Brute force is possible but highly inefficient; enumerating all subarrays leads to O(n^2) time and duplicates that must be filtered.

Why does the solution only track ORs of previous subarrays?

OR values are monotonic in bits, so storing only previous ORs allows computing new values without recomputing every subarray.

How do bit manipulation and DP combine in this problem?

Bit manipulation ensures OR accumulation is correct while DP tracks intermediate OR sets efficiently across array indices.

What are common mistakes in interview implementations?

Including redundant subarrays, failing to merge OR results into the global set, and overestimating space usage are frequent errors.

terminal

Solution

Solution 1: Hash Table

The problem asks for the number of unique bitwise OR operations results of subarrays. If we enumerate the end position $i$ of the subarray, the number of bitwise OR operations results of the subarray ending at $i-1$ does not exceed $32$. This is because the bitwise OR operation is a monotonically increasing operation.

1

2

3

4

5

6

7

8

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

Continue Practicing

#943 find the shortest superstring #805 split array with same average #996 number of squareful arrays