Watch 2 video solutions for Find Subarray With Bitwise OR Closest to K, a hard level problem involving Array, Binary Search, Bit Manipulation. This walkthrough by Coder on A Farm has 236 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |