How does binary search apply to the problem of finding a subarray with the bitwise OR closest to k?

Binary search can be used to narrow down the range of possible OR values, optimizing the search for the subarray that minimizes the absolute difference from k.

What is the significance of dynamic programming in this problem?

Dynamic programming helps track all bitwise OR values of subarrays efficiently, which is essential for finding the minimal absolute difference from k in large arrays.

What are the main challenges in solving the Find Subarray With Bitwise OR Closest to K problem?

The main challenges include efficiently computing the bitwise OR for subarrays and managing large input sizes with optimal time complexity.

What optimizations can be applied to improve the performance of this problem?

Using binary search over the possible OR values and efficient range queries with dynamic programming or segment trees can significantly improve performance.

How do you handle the large constraints in the Find Subarray With Bitwise OR Closest to K problem?

Handling the large constraints requires optimizing the solution using binary search, dynamic programming, or segment trees to ensure the solution scales well with the input size.

#3171

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

找到按位或最接近 K 的子数组

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，满足子数组中所有元素按位或运算 OR 的值与 k 的绝对差尽可能小。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r…

数组二分查找位运算线段树

题目描述

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能小。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回最小的绝对差值。

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

示例 1：

输入：nums = [1,2,4,5], k = 3

输出：0

解释：

子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入：nums = [1,3,1,3], k = 2

输出：1

解释：

子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：

输入：nums = [1], k = 10

输出：9

解释：

只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

lightbulb

解题思路

方法一：双指针 + 位运算

根据题目描述，我们需要求出数组 $\textit{nums}$ 下标 $l$ 到 $r$ 的元素的按位或运算的结果，即 $\textit{nums}[l] \lor \textit{nums}[l + 1] \lor \cdots \lor \textit{nums}[r]$ 。其中 $\lor$ 表示按位或运算。

如果我们每次固定右端点 $r$ ，那么左端点 $l$ 的范围是 $[0, r]$ 。每次移动右端点 $r$ ，按位或的结果只会变大，我们用一个变量 $s$ 记录当前的按位或的结果，如果 $s$ 大于 $k$ ，我们就将左端点 $l$ 向右移动，直到 $s$ 小于等于 $k$ 。在移动左端点 $l$ 的过程中，我们需要维护一个数组 $cnt$ ，记录当前区间内每个二进制位上 $0$ 的个数，当 $cnt[h]$ 为 $0$ 时，说明当前区间内的元素在第 $h$ 位上都为 $0$ ，我们就可以将 $s$ 的第 $h$ 位设置为 $0$ 。

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

相似题目：

3097. 或值至少为 K 的最短子数组 II

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        m = max(nums).bit_length()
        cnt = [0] * m
        s = i = 0
        ans = inf
        for j, x in enumerate(nums):
            s |= x
            ans = min(ans, abs(s - k))
            for h in range(m):
                if x >> h & 1:
                    cnt[h] += 1
            while i < j and s > k:
                y = nums[i]
                for h in range(m):
                    if y >> h & 1:
                        cnt[h] -= 1
                        if cnt[h] == 0:
                            s ^= 1 << h
                i += 1
                ans = min(ans, abs(s - k))
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate uses binary search effectively to narrow down the possible range of OR values.
question_mark
They demonstrate a solid understanding of bitwise operations and their implications for array manipulation.
question_mark
The candidate proposes an efficient way to track the OR values for multiple subarrays, possibly with dynamic programming or a segment tree.

warning

常见陷阱

外企场景

error
Not considering the need for efficient range queries can lead to suboptimal performance.
error
Failing to recognize the potential optimization of binary search over the OR values might result in slower solutions.
error
Misunderstanding the problem's constraints may lead to an approach that doesn't scale with larger arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find the subarray that minimizes the sum of bitwise OR values across subarrays.
arrow_right_alt
Introduce multiple target values for k, requiring the solution to handle multiple queries in the same problem.
arrow_right_alt
Optimize the solution further by reducing the space complexity, potentially eliminating the need for dynamic programming.

help

常见问题

外企场景

继续练习

#3209 子数组按位与值为 K 的数目 #3117 划分数组得到最小的值之和 #3161 物块放置查询