# Find Subarray With Bitwise OR Closest to K
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-subarray-with-bitwise-or-closest-to-k)
Canonical: https://scaleengineer.com/dsa/problems/find-subarray-with-bitwise-or-closest-to-k
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree
---
## 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 <= 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= 109`

# Approaches
## Brute Force Enumeration of Subarrays
The most direct way to solve the problem is to consider every possible non-empty subarray, calculate the bitwise OR of its elements, and find the absolute difference between this OR value and `k`. We keep track of the minimum difference found so far.
**Time:** O(N^2), where N is the length of the `nums` array. The two nested loops iterate through all possible O(N^2) subarrays. The bitwise OR operation inside the inner loop takes constant time. · **Space:** O(1), as we only use a few variables to store the state (`minDiff`, `currentOr`, loop indices).
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large inputs. With N up to 10^5, an O(N^2) solution will be too slow and result in a "Time Limit Exceeded" error.
### Explanation
We can use two nested loops to define the start and end of each subarray. The outer loop iterates through all possible starting indices `l` from `0` to `n-1`, and the inner loop iterates through all possible ending indices `r` from `l` to `n-1`. For each subarray `nums[l..r]`, we compute the bitwise OR of its elements. To do this efficiently, within the inner loop, we can maintain a running OR value that gets updated with each new element. After calculating the OR for a subarray, we compute its absolute difference with `k` and update our overall minimum difference if the new difference is smaller.

```java
class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        int minDiff = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int currentOr = 0;
            for (int j = i; j < n; j++) {
                currentOr |= nums[j];
                minDiff = Math.min(minDiff, Math.abs(currentOr - k));
            }
        }
        return minDiff;
    }
}
```
### Algorithm
- Initialize a variable `min_diff` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through the array with an index `l` from `0` to `n-1` (representing the start of the subarray).
- Inside this loop, initialize `current_or = 0`.
- Start a nested loop with an index `r` from `l` to `n-1` (representing the end of the subarray).
- Update the running OR: `current_or = current_or | nums[r]`.
- Calculate the difference: `diff = Math.abs(current_or - k)`.
- Update the minimum difference: `min_diff = Math.min(min_diff, diff)`.
- After the loops complete, `min_diff` holds the result.

## Optimized Approach with Set of OR Prefixes
This approach significantly improves upon the brute-force method by leveraging a key property of the bitwise OR operation. For any fixed ending index `i`, the number of distinct OR values for all subarrays `nums[j...i]` (where `0 <= j <= i`) is very small. This is because the sequence of OR values `OR(i,i), OR(i-1,i), OR(i-2,i), ...` is non-decreasing. A new distinct value can only be formed if a new bit is set to 1. Since the input numbers are up to 10^9 (which fits within 30 bits), there can be at most 30 distinct values in this sequence.
**Time:** O(N * B), where N is the length of `nums` and B is the number of bits in the integer type (e.g., 30 for numbers up to 10^9). The outer loop runs N times. The size of the `prevOrs` set is bounded by B, so the inner loops run at most B times. This is highly efficient. · **Space:** O(B), for storing the `prevOrs` and `currentOrs` sets. The size of these sets is bounded by B, where B is the number of bits in the integer type (around 30).
**Pros:** Very efficient, passes the time limits for large constraints.
**Cons:** The logic is more complex to understand compared to the brute-force approach. It relies on a non-obvious property of the bitwise OR operation.
### Explanation
We can iterate through the input array `nums` from left to right. At each index `i`, we maintain a set of all distinct OR values of subarrays that end at the *previous* index, `i-1`. Let's call this set `prev_ors`. To find the distinct OR values for subarrays ending at the current index `i`, we create a new set, `current_ors`. This new set is formed by:
1.  The value `nums[i]` itself (for the subarray `[i,i]`).
2.  The values `val | nums[i]` for every `val` in `prev_ors`.
As we compute the values for `current_ors`, we also update our global `min_diff` by comparing each new OR value with `k`. After processing index `i`, `current_ors` becomes `prev_ors` for the next iteration. Because the size of these sets is small (at most ~30), the overall complexity is much better than the brute-force approach.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int minDiff = Integer.MAX_VALUE;
        // This set stores the distinct OR values of all subarrays ending at the previous index.
        Set<Integer> prevOrs = new HashSet<>();

        for (int num : nums) {
            Set<Integer> currentOrs = new HashSet<>();
            // The OR value of the subarray containing just the current number.
            currentOrs.add(num);
            
            // For each distinct OR value of subarrays ending at the previous index,
            // calculate the new OR value by including the current number.
            for (int prevOr : prevOrs) {
                currentOrs.add(prevOr | num);
            }

            // For each new distinct OR value, update the minimum difference.
            for (int orVal : currentOrs) {
                minDiff = Math.min(minDiff, Math.abs(orVal - k));
            }
            
            // The current set of ORs becomes the previous set for the next iteration.
            prevOrs = currentOrs;
        }

        return minDiff;
    }
}
```
### Algorithm
- Initialize `min_diff` to `Integer.MAX_VALUE`.
- Initialize an empty set, `prev_ors`, to store distinct OR values of subarrays ending at the previous index.
- Iterate through each `num` in the `nums` array.
- Create a new empty set, `current_ors`.
- Add `num` to `current_ors`.
- For each `or_val` in `prev_ors`, add `or_val | num` to `current_ors`.
- For each `val` in `current_ors`, update `min_diff = Math.min(min_diff, Math.abs(val - k))`.
- Set `prev_ors = current_ors` to prepare for the next iteration.
- Return `min_diff`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```