Find Subarray With Bitwise OR Closest to K solution and explanation
The problem
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
Approach overview
Problem 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 1: Approach 1: Brute Force with Prefix OR Computation
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.
def min_absolute_difference(nums, k):
min_diff = float('inf')
for i in range(len(nums)):
current_or = 0
for j in range(i, len(nums)):
current_or |= nums[j]
current_diff = abs(current_or - k)
min_diff = min(min_diff, current_diff)
return min_diff
nums = [1, 2, 4, 5]
k = 3
print(min_absolute_difference(nums, k))import java.util.*;
public class Main {
public static int minAbsoluteDifference(int[] nums, int k) {
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int currentOR = 0;
for (int j = i; j < nums.length; j++) {
currentOR |= nums[j];
int currentDiff = Math.abs(currentOR - k);
minDiff = Math.min(minDiff, currentDiff);
}
}
return minDiff;
}
public static void main(String[] args) {
int[] nums = {1, 2, 4, 5};
int k = 3;
System.out.println(minAbsoluteDifference(nums, k));
}
}#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
int minAbsoluteDifference(std::vector<int>& nums, int k) {
int minDiff = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
int currentOR = 0;
for (int j = i; j < nums.size(); j++) {
currentOR |= nums[j];
int currentDiff = std::abs(currentOR - k);
minDiff = std::min(minDiff, currentDiff);
}
}
return minDiff;
}
int main() {
std::vector<int> nums = {1, 2, 4, 5};
int k = 3;
std::cout << minAbsoluteDifference(nums, k) << std::endl;
return 0;
}function minAbsoluteDifference(nums, k) {
let minDiff = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length; i++) {
let currentOR = 0;
for (let j = i; j < nums.length; j++) {
currentOR |= nums[j];
let currentDiff = Math.abs(currentOR - k);
minDiff = Math.min(minDiff, currentDiff);
}
}
return minDiff;
}
let nums = [1, 2, 4, 5];
let k = 3;
console.log(minAbsoluteDifference(nums, k));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minAbsoluteDifference(int* nums, int numsSize, int k) {
int minDiff = INT_MAX;
for (int i = 0; i < numsSize; i++) {
int currentOR = 0;
for (int j = i; j < numsSize; j++) {
currentOR |= nums[j];
int currentDiff = abs(currentOR - k);
if (currentDiff < minDiff) {
minDiff = currentDiff;
}
}
}
return minDiff;
}
int main() {
int nums[] = {1, 2, 4, 5};
int k = 3;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minAbsoluteDifference(nums, numsSize, k));
return 0;
}using System;
public class Solution {
public static int MinAbsoluteDifference(int[] nums, int k) {
int minDiff = int.MaxValue;
for (int i = 0; i < nums.Length; i++) {
int currentOR = 0;
for (int j = i; j < nums.Length; j++) {
currentOR |= nums[j];
int currentDiff = Math.Abs(currentOR - k);
minDiff = Math.Min(minDiff, currentDiff);
}
}
return minDiff;
}
public static void Main() {
int[] nums = {1, 2, 4, 5};
int k = 3;
Console.WriteLine(MinAbsoluteDifference(nums, k));
}
}The function min_absolute_difference calculates the minimal absolute difference between k and the OR of elements in the subarrays of nums. Each subarray OR is calculated by extending current OR with a new element.
Time Complexity: O(n^2), due to checking all subarrays.
Space Complexity: O(1), as no additional data structures are used.
Approach 2: Approach 2: Two-Pointer Technique
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.
def min_absolute_difference(nums, k):
min_diff = float('inf')
left = 0
current_or = 0
for right in range(len(nums)):
current_or |= nums[right]
while left <= right and current_or > k:
min_diff = min(min_diff, abs(current_or - k))
current_or &= ~nums[left]
left += 1
min_diff = min(min_diff, abs(current_or - k))
return min_diff
nums = [1, 3, 1, 3]
k = 2
print(min_absolute_difference(nums, k))public class Main {
public static int minAbsoluteDifference(int[] nums, int k) {
int minDiff = Integer.MAX_VALUE;
int currentOR = 0;
for (int left = 0, right = 0; right < nums.length; right++) {
currentOR |= nums[right];
while (left <= right && currentOR > k) {
minDiff = Math.min(minDiff, Math.abs(currentOR - k));
currentOR &= ~nums[left++];
}
minDiff = Math.min(minDiff, Math.abs(currentOR - k));
}
return minDiff;
}
public static void main(String[] args) {
int[] nums = {1, 3, 1, 3};
int k = 2;
System.out.println(minAbsoluteDifference(nums, k));
}
}#include <iostream>
#include <vector>
#include <climits>
int minAbsoluteDifference(std::vector<int>& nums, int k) {
int minDiff = INT_MAX;
int left = 0, currentOR = 0;
for (int right = 0; right < nums.size(); right++) {
currentOR |= nums[right];
while (left <= right && currentOR > k) {
minDiff = std::min(minDiff, abs(currentOR - k));
currentOR &= ~nums[left++];
}
minDiff = std::min(minDiff, abs(currentOR - k));
}
return minDiff;
}
int main() {
std::vector<int> nums = {1, 3, 1, 3};
int k = 2;
std::cout << minAbsoluteDifference(nums, k) << std::endl;
return 0;
}function minAbsoluteDifference(nums, k) {
let minDiff = Number.MAX_SAFE_INTEGER;
let currentOR = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
currentOR |= nums[right];
while (left <= right && currentOR > k) {
minDiff = Math.min(minDiff, Math.abs(currentOR - k));
currentOR &= ~nums[left++];
}
minDiff = Math.min(minDiff, Math.abs(currentOR - k));
}
return minDiff;
}
let nums = [1, 3, 1, 3];
let k = 2;
console.log(minAbsoluteDifference(nums, k));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minAbsoluteDifference(int* nums, int numsSize, int k) {
int minDiff = INT_MAX;
int left = 0, currentOR = 0;
for (int right = 0; right < numsSize; right++) {
currentOR |= nums[right];
while (left <= right && currentOR > k) {
int currentDiff = abs(currentOR - k);
minDiff = minDiff < currentDiff ? minDiff : currentDiff;
currentOR &= ~nums[left++];
}
int currentDiff = abs(currentOR - k);
minDiff = minDiff < currentDiff ? minDiff : currentDiff;
}
return minDiff;
}
int main() {
int nums[] = {1, 3, 1, 3};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minAbsoluteDifference(nums, numsSize, k));
return 0;
}using System;
public class Solution {
public static int MinAbsoluteDifference(int[] nums, int k) {
int minDiff = int.MaxValue;
int left = 0, currentOR = 0;
for (int right = 0; right < nums.Length; right++) {
currentOR |= nums[right];
while (left <= right && currentOR > k) {
minDiff = Math.Min(minDiff, Math.Abs(currentOR - k));
currentOR &= ~nums[left++];
}
minDiff = Math.Min(minDiff, Math.Abs(currentOR - k));
}
return minDiff;
}
public static void Main() {
int[] nums = {1, 3, 1, 3};
int k = 2;
Console.WriteLine(MinAbsoluteDifference(nums, k));
}
}The function follows a two-pointer method to slide a window over the array and efficiently calculate OR values for the subarrays. The minimal absolute difference is calculated dynamically.
Time Complexity: O(n), due to efficient window resizing.
Space Complexity: O(1), requiring constant extra storage only.
Approach 3: 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 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:
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;
}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
}Approach 4: 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 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:
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Prefix OR Computation | Time Complexity: O(n^2), due to checking all subarrays. |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n), due to efficient window resizing. |
| Two Pointers + Bitwise Operations | – |
| Hash Table + Enumeration | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Subarray With Bitwise OR Closest to K easy or hard?
This problem is considered Hard because maintaining the bitwise OR while dynamically shrinking a window is non-trivial. The challenge comes from the fact that OR is not reversible, so you must track bit frequencies to correctly update the window value.
Find Subarray With Bitwise OR Closest to K Python/Java solution
Python, Java, C++, and other languages implement the same logic: maintain a sliding window and an array of 32 counters for bit frequencies. When adding or removing numbers from the window, update the counters and recompute the OR value. Track the minimum absolute difference from k during traversal.
How to solve Find Subarray With Bitwise OR Closest to K in O(n)?
Strict O(n) is difficult because maintaining a dynamic bitwise OR requires checking bit positions. The practical optimal solution runs in O(n * 32) using a sliding window and a frequency array for each bit. Each element updates the 32-bit counters when entering or leaving the window, allowing fast recomputation of the current OR.
What is the best approach for Find Subarray With Bitwise OR Closest to K?
The most efficient approach uses a sliding window (two-pointer technique) combined with bit frequency tracking. Each bit position (0–31) keeps a count of how many elements in the window contain that bit. This allows recomputing the window OR in constant time when expanding or shrinking the window. The overall complexity becomes O(n * 32).
Is Find Subarray With Bitwise OR Closest to K asked at Google/Amazon/Meta?
Problems involving subarray bitwise operations and sliding windows frequently appear in interviews at large tech companies. Variants of this problem test understanding of bit manipulation, window maintenance, and monotonic properties of OR operations, which are common themes in Google and Amazon coding interviews.
What data structure is used in Find Subarray With Bitwise OR Closest to K?
The optimized solution uses a sliding window with a small fixed-size array (size 32) to track bit frequencies. This acts like a lightweight counter structure for each bit position. Standard array traversal and bit manipulation operations are used to maintain the window OR efficiently.
What is the time complexity of Find Subarray With Bitwise OR Closest to K?
The brute force method checks every subarray and runs in O(n²) time. The optimized sliding window solution tracks bit counts and processes each element once when entering and leaving the window. Since each update touches at most 32 bits, the time complexity is O(n * 32) with O(32) extra space.