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 <= 1051 <= nums[i] <= 1091 <= k <= 109
Solutions
Solution 1: Two Pointers + Bitwise Operations
According to the problem description, we need to calculate the result of the bitwise OR operation of elements from index $l$ to $r$ in the array $\textit{nums}$, that is, $\textit{nums}[l] \lor \textit{nums}[l + 1] \lor \cdots \lor \textit{nums}[r]$, where $\lor$ represents the bitwise OR operation.
If we fix the right endpoint $r$, then the range of the left endpoint $l$ is $[0, r]$. Each time we move the right endpoint $r$, the result of the bitwise OR operation will only increase. We use a variable $s$ to record the current result of the bitwise OR operation. If $s$ is greater than $k$, we move the left endpoint $l$ to the right until $s$ is less than or equal to $k$. During the process of moving the left endpoint $l$, we need to maintain an array $cnt$ to record the number of $0$s on each binary digit in the current interval. When $cnt[h] = 0$, it means that all elements in the current interval have a $0$ on the $h^{th}$ bit, and we can set the $h^{th}$ bit of $s$ to $0$.
The time complexity is $O(n \times \log M)$, and the space complexity is $O(\log M)$. Here, $n$ and $M$ respectively represent the length of the array $\textit{nums}$ and the maximum value in the array $\textit{nums}$.
Similar Problems:
Python3
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
Java
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 = 0; 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) == 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;
}
}
++i;
ans = Math.min(ans, Math.abs(s - k));
}
}
return ans;
}
}
C++
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 = 0; j < n; ++j) {
s |= nums[j];
ans = min(ans, abs(s - k));
for (int h = 0; h < m; ++h) {
if (nums[j] >> h & 1) {
++cnt[h];
}
}
while (i < j && s > k) {
for (int h = 0; h < m; ++h) {
if (nums[i] >> h & 1 && --cnt[h] == 0) {
s ^= 1 << h;
}
}
ans = min(ans, abs(s - k));
++i;
}
}
return ans;
}
};
Go
func minimumDifference(nums []int, k int) int {
m := bits.Len(uint(slices.Max(nums)))
cnt := make([]int, m)
ans := math.MaxInt32
s, i := 0, 0
for j, x := range nums {
s |= x
ans = min(ans, abs(s-k))
for h := 0; h < m; h++ {
if x>>h&1 == 1 {
cnt[h]++
}
}
for i < j && s > k {
y := nums[i]
for h := 0; h < m; h++ {
if y>>h&1 == 1 {
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
}
TypeScript
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 = 0; 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) {
++cnt[h];
}
}
while (i < j && s > k) {
for (let h = 0; h < m; ++h) {
if ((nums[i] >> h) & 1 && --cnt[h] === 0) {
s ^= 1 << h;
}
}
ans = Math.min(ans, Math.abs(s - k));
++i;
}
}
return ans;
}
Solution 2: Hash Table + Enumeration
According to the problem description, we need to calculate the result of the bitwise OR operation of elements from index $l$ to $r$ in the array $nums$, that is, $nums[l] \lor nums[l + 1] \lor \cdots \lor nums[r]$. Here, $\lor$ represents the bitwise OR operation.
If we fix the right endpoint $r$, then the range of the left endpoint $l$ is $[0, r]$. Since the sum of bitwise OR increases monotonically as $l$ decreases, and the value of $\textit{nums}[i]$ does not exceed $10^9$, the interval $[0, r]$ can have at most $30$ different values. Therefore, we can use a set to maintain all the values of $nums[l] \lor nums[l + 1] \lor \cdots \lor nums[r]$. When we traverse from $r$ to $r+1$, the values with $r+1$ as the right endpoint are the values obtained by performing the bitwise OR operation of each value in the set with $nums[r + 1]$, plus $nums[r + 1]$ itself. Therefore, we only need to enumerate each value in the set and perform the bitwise OR operation with $nums[r]$, to get all the values for $r$ as the right endpoint. Then, we take the absolute difference of each value with $k$, and the minimum of these differences is the answer.
The time complexity is $O(n \times \log M)$, and the space complexity is $O(\log M)$. Here, $n$ and $M$ respectively represent the length of the array $nums$ and the maximum value in the array $nums$.
Similar Problems:
Python3
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
ans = inf
s = set()
for x in nums:
s = {x | y for y in s} | {x}
ans = min(ans, min(abs(y - k) for y in s))
return ans
Java
class Solution {
public int minimumDifference(int[] nums, int k) {
int ans = Integer.MAX_VALUE;
Set<Integer> pre = new HashSet<>();
for (int x : nums) {
Set<Integer> cur = new HashSet<>();
for (int y : pre) {
cur.add(x | y);
}
cur.add(x);
for (int y : cur) {
ans = Math.min(ans, Math.abs(y - k));
}
pre = cur;
}
return ans;
}
}
C++
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int ans = INT_MAX;
unordered_set<int> pre;
for (int x : nums) {
unordered_set<int> cur;
cur.insert(x);
for (int y : pre) {
cur.insert(x | y);
}
for (int y : cur) {
ans = min(ans, abs(y - k));
}
pre = move(cur);
}
return ans;
}
};
Go
func minimumDifference(nums []int, k int) int {
ans := math.MaxInt32
pre := map[int]bool{}
for _, x := range nums {
cur := map[int]bool{x: true}
for y := range pre {
cur[x|y] = true
}
for y := range cur {
ans = min(ans, max(y-k, k-y))
}
pre = cur
}
return ans
}
TypeScript
function minimumDifference(nums: number[], k: number): number {
let ans = Infinity;
let pre = new Set<number>();
for (const x of nums) {
const cur = new Set<number>();
cur.add(x);
for (const y of pre) {
cur.add(x | y);
}
for (const y of cur) {
ans = Math.min(ans, Math.abs(y - k));
}
pre = cur;
}
return ans;
}