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.

#898

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

子数组按位或操作

给定一个整数数组 arr ，返回所有 arr 的非空子数组的不同按位或的数量。子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。子数组是数组内连续的非空元素序列。示例 1：输入： arr = [0] 输出： 1 解释：只有一个可能的结果 0 。示例 2：…

数组动态规划位运算

题目描述

给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。

子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。

子数组 是数组内连续的非空元素序列。

示例 1：

输入：arr = [0]
输出：1
解释：
只有一个可能的结果 0 。

示例 2：

输入：arr = [1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例 3：

输入：arr = [1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

提示：

1 <= nums.length <= 5 * 10⁴
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：哈希表

题目求的是子数组按位或操作的结果的数量，如果我们枚举子数组的结束位置 $i$ ，那么以 $i-1$ 结尾的子数组按位或操作的结果的数量最多不超过 $32$ 个。这是因为，按位或是一个单调递增的操作。

因此，我们用一个哈希表 $ans$ 记录所有子数组按位或操作的结果，用一个哈希表 $s$ 记录以当前元素结尾的子数组按位或操作的结果，初始时 $s$ 只包含一个元素 $0$ 。

接下来，我们枚举子数组的结束位置 $i$ ，那么以 $i$ 结尾的子数组按位或操作的结果，是以 $i-1$ 结尾的子数组按位或操作的结果与 $a[i]$ 进行按位或操作的结果的集合，再加上 $a[i]$ 本身。我们用一个哈希表 $t$ 记录以 $i$ 结尾的子数组按位或操作的结果，然后我们更新 $s = t$ ，并将 $t$ 中的所有元素加入 $ans$ 。

最终，我们返回哈希表 $ans$ 中元素的数量即可。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(n \times \log M)$ 。其中 $n$ 和 $M$ 分别为数组长度和数组中元素的最大值。

1

2

3

4

5

6

7

8

9

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#943 最短超级串 #805 数组的均值分割 #996 平方数组的数目