# 3171. Find Subarray With Bitwise OR Closest to K

## Description

You are given an array nums and an integer k. You need to find a subarray of nums such that the absolute difference between k and the bitwise OR of the subarray elements is as small as possible. In other words, select a subarray nums[l..r] such that \|k - (nums[l] OR nums[l + 1] ... OR nums[r])\| is minimum.

Return the minimum possible value of the absolute difference.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,4,5], k = 3

Output: 0

Explanation:

The subarray nums[0..1] has OR value 3, which gives the minimum absolute difference \|3 - 3\| = 0.

Example 2:

Input: nums = [1,3,1,3], k = 2

Output: 1

Explanation:

The subarray nums[1..1] has OR value 3, which gives the minimum absolute difference \|3 - 2\| = 1.

Example 3:

Input: nums = [1], k = 10

Output: 9

Explanation:

There is a single subarray with OR value 1, which gives the minimum absolute difference \|10 - 1\| = 9.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

## Solutions

### Solution 1: Two Pointers + Bitwise Operation

According to the problem description, we need to find the bitwise AND operation result of the elements from index $l$ to $r$ in the array $nums$, i.e., $nums[l] \& nums[l + 1] \& \cdots \& nums[r]$.

If we fix the right endpoint $r$ each time, then the range of the left endpoint $l$ is $[0, r]$. Each time we move the right endpoint $r$, the bitwise AND result will only decrease. We use a variable $s$ to record the current bitwise AND result. If $s$ is less than $k$, we move the left endpoint $l$ to the right until $s$ is greater than or equal to $k$. In the process of moving the left endpoint $l$, we need to maintain an array $cnt$ to record the number of $0$s at each binary digit in the current interval. When $cnt[h]$ is $0$, it means that the elements in the current interval are all $1$ at the $h$th digit, and we can set the $h$th digit of $s$ to $1$.

The time complexity is $O(n \times \log M)$, and the space complexity is $O(\log M)$. Where $n$ and $M$ are the length of the array $nums$ and the maximum value in the array $nums$ respectively.

Similar Problems:

• class Solution {
public int minimumDifference(int[] nums, int k) {
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, x);
}
int m = 32 - Integer.numberOfLeadingZeros(mx);
int[] cnt = new int[m];
int n = nums.length;
int ans = Integer.MAX_VALUE;
for (int i = 0, j = 0, s = -1; j < n; ++j) {
s &= nums[j];
ans = Math.min(ans, Math.abs(s - k));
for (int h = 0; h < m; ++h) {
if ((nums[j] >> h & 1) == 0) {
++cnt[h];
}
}
while (i < j && s < k) {
for (int h = 0; h < m; ++h) {
if ((nums[i] >> h & 1) == 0 && --cnt[h] == 0) {
s |= 1 << h;
}
}
++i;
ans = Math.min(ans, Math.abs(s - k));
}
}
return ans;
}
}

• class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int mx = *max_element(nums.begin(), nums.end());
int m = 32 - __builtin_clz(mx);
int n = nums.size();
int ans = INT_MAX;
vector<int> cnt(m);
for (int i = 0, j = 0, s = -1; j < n; ++j) {
s &= nums[j];
ans = min(ans, abs(s - k));
for (int h = 0; h < m; ++h) {
if (nums[j] >> h & 1 ^ 1) {
++cnt[h];
}
}
while (i < j && s < k) {
for (int h = 0; h < m; ++h) {
if (nums[i] >> h & 1 ^ 1 && --cnt[h] == 0) {
s |= 1 << h;
}
}
ans = min(ans, abs(s - k));
++i;
}
}
return ans;
}
};

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


• func minimumDifference(nums []int, k int) int {
m := bits.Len(uint(slices.Max(nums)))
cnt := make([]int, m)
ans := math.MaxInt32
s, i := -1, 0
for j, x := range nums {
s &= x
ans = min(ans, abs(s-k))
for h := 0; h < m; h++ {
if x>>h&1 == 0 {
cnt[h]++
}
}
for i < j && s < k {
y := nums[i]
for h := 0; h < m; h++ {
if y>>h&1 == 0 {
cnt[h]--
if cnt[h] == 0 {
s |= 1 << h
}
}
}
ans = min(ans, abs(s-k))
i++
}
}
return ans
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}

• function minimumDifference(nums: number[], k: number): number {
const m = Math.max(...nums).toString(2).length;
const n = nums.length;
const cnt: number[] = Array(m).fill(0);
let ans = Infinity;
for (let i = 0, j = 0, s = -1; j < n; ++j) {
s &= nums[j];
ans = Math.min(ans, Math.abs(s - k));
for (let h = 0; h < m; ++h) {
if (((nums[j] >> h) & 1) ^ 1) {
++cnt[h];
}
}
while (i < j && s < k) {
for (let h = 0; h < m; ++h) {
if (((nums[i] >> h) & 1) ^ 1 && --cnt[h] === 0) {
s |= 1 << h;
}
}
ans = Math.min(ans, Math.abs(s - k));
++i;
}
}
return ans;
}