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 <= 109This approach involves using a nested loop to evaluate each possible subarray of the given array. We start at each index and calculate the OR value progressively by including more elements. A prefix OR allows us to efficiently compute the OR value for each subarray.
The function minAbsoluteDifference calculates the minimum absolute difference between k and the OR value of subarrays of nums. It iteratively evaluates each subarray, updating the minimum difference found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the size of the input array.
Space Complexity: O(1), as we're not using any additional space proportional to the input size.
This method uses a two-pointer technique to efficiently iterate through possible subarrays. We maintain a window with a left and right boundary, updating our OR value incrementally as we adjust the window to minimize the difference with k.
The two-pointer technique creates a dynamic window over the subarray to efficiently adjust the OR value. If this OR surpasses k, it adjusts the window to decrease its size from the left side.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), since we process each element at most twice.
Space Complexity: O(1), as our only additional storage is a few integer variables.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Prefix OR Computation | Time Complexity: O(n^2), where n is the size of the input array. |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n), since we process each element at most twice. |
Count Subarray sum Equals K | Brute - Better -Optimal • take U forward • 446,156 views views
Watch 9 more video solutions →Practice Find Subarray With Bitwise OR Closest to K with our built-in code editor and test cases.
Practice on FleetCode