Welcome to Subscribe On Youtube
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 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; }