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 assmall 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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

Solution

Method 1 – Sliding Window with Set of ORs

Intuition

For each subarray, the bitwise OR can only increase or stay the same as we extend the subarray. We can use a set to keep all possible ORs ending at each position, and for each, check the absolute difference to k.

Approach

  1. Initialize a set to keep all possible ORs ending at the previous position.
  2. For each number in nums, create a new set of ORs by OR-ing the current number with all ORs from the previous set, and also include the current number itself.
  3. For each OR value, update the minimum absolute difference to k.
  4. Return the minimum difference found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int closestToK(vector<int>& nums, int k) {
        int ans = INT_MAX;
        unordered_set<int> prev;
        for (int x : nums) {
            unordered_set<int> cur = {x};
            for (int v : prev) cur.insert(v | x);
            for (int v : cur) ans = min(ans, abs(v - k));
            prev = cur;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func closestToK(nums []int, k int) int {
    ans := 1<<31 - 1
    prev := map[int]struct{}{}
    for _, x := range nums {
        cur := map[int]struct{}{x: {}}
        for v := range prev {
            cur[v|x] = struct{}{}
        }
        for v := range cur {
            if abs(v-k) < ans {
                ans = abs(v-k)
            }
        }
        prev = cur
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int closestToK(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        Set<Integer> prev = new HashSet<>();
        for (int x : nums) {
            Set<Integer> cur = new HashSet<>();
            cur.add(x);
            for (int v : prev) cur.add(v | x);
            for (int v : cur) ans = Math.min(ans, Math.abs(v - k));
            prev = cur;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun closestToK(nums: IntArray, k: Int): Int {
        var ans = Int.MAX_VALUE
        var prev = mutableSetOf<Int>()
        for (x in nums) {
            val cur = mutableSetOf(x)
            for (v in prev) cur.add(v or x)
            for (v in cur) ans = minOf(ans, kotlin.math.abs(v - k))
            prev = cur
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def closestToK(self, nums: list[int], k: int) -> int:
        ans = float('inf')
        prev = set()
        for x in nums:
            cur = {x}
            for v in prev:
                cur.add(v | x)
            for v in cur:
                ans = min(ans, abs(v - k))
            prev = cur
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn closest_to_k(nums: Vec<i32>, k: i32) -> i32 {
        let mut ans = i32::MAX;
        let mut prev = std::collections::HashSet::new();
        for &x in &nums {
            let mut cur = std::collections::HashSet::new();
            cur.insert(x);
            for &v in &prev { cur.insert(v | x); }
            for &v in &cur { ans = ans.min((v - k).abs()); }
            prev = cur;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    closestToK(nums: number[], k: number): number {
        let ans = Infinity;
        let prev = new Set<number>();
        for (const x of nums) {
            const cur = new Set<number>([x]);
            for (const v of prev) cur.add(v | x);
            for (const v of cur) ans = Math.min(ans, Math.abs(v - k));
            prev = cur;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * W), where n is the length of nums and W is the number of unique OR values per position (at most 32 for 32-bit integers).
  • 🧺 Space complexity: O(W), for the set of OR values.