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 <= 109Problem Overview: You are given an integer array and a value k. The goal is to choose a contiguous subarray whose bitwise OR is as close as possible to k. Instead of matching exactly, you minimize |OR - k| across all possible subarrays.
Approach 1: Brute Force with Prefix OR Computation (Time: O(n²), Space: O(1))
Enumerate every subarray starting at index i. Maintain a running OR value while extending the end index j. Because OR is monotonic when expanding a window (a | b | c never removes bits), you can reuse the previous OR instead of recomputing from scratch. For each extension, compute abs(current_or - k) and update the minimum difference. This approach is straightforward and demonstrates the key observation about OR accumulation, but it still checks O(n²) subarrays. It works for small inputs and is useful for validating optimized logic. The solution relies heavily on array traversal and bit manipulation behavior.
Approach 2: Two-Pointer Technique with Bit Tracking (Time: O(n * 32), Space: O(32))
Use a sliding window where the right pointer expands the subarray and the left pointer shrinks it. Since OR only increases when adding elements, you track how many times each bit (0–31) appears inside the window. When a number enters the window, increment counts for its set bits and recompute the current OR. When the window needs to shrink, decrement those counts; if a bit count becomes zero, remove that bit from the window OR. Each step updates the minimum difference with k. Because each element enters and leaves the window once and bit operations are limited to 32 positions, the total work becomes O(n * 32). This pattern combines sliding window logic with efficient bit accounting and is common in advanced bit manipulation problems.
Recommended for interviews: Start with the brute force explanation to show you understand how OR accumulates across subarrays. Then transition to the optimized sliding window with bit counts. Interviewers usually expect the optimized approach because it demonstrates deeper understanding of OR monotonicity, window maintenance, and efficient bit-level updates.
This 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.
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.
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.
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], 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 0s 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 nums and the maximum value in the array nums.
Similar Problems:
Python
Java
C++
Go
TypeScript
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 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:
Python
Java
C++
Go
TypeScript
| 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. |
| Two Pointers + Bitwise Operations | — |
| Hash Table + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Incremental OR | O(n²) | O(1) | Useful for understanding OR accumulation and validating logic on small inputs |
| Two-Pointer with Bit Frequency Tracking | O(n * 32) | O(32) | Best general solution for large arrays; maintains window OR efficiently |
leetcode 3171 Find Subarray With Bitwise OR Closest to K • Coder on A Farm • 236 views views
Watch 1 more video solutions →Practice Find Subarray With Bitwise OR Closest to K with our built-in code editor and test cases.
Practice on FleetCode