Find Subarray With Bitwise OR Closest to K

Hard
745.

Find Subarray With Bitwise OR Closest to K

Find Subarray With Bitwise OR Closest to K is a hard coding problem on arrays, binary search and bit manipulation, asked in Amazon, Google and Meta interviews.

Over all non-empty subarrays of nums, minimise |(bitwise OR of the subarray) - k|.

Return that minimum value.

Example 1

Input
nums = [1,2,4,5], k = 3
Output
0
Explanation
The subarray [1,2] ORs to exactly 3.

Example 2

Input
nums = [1,3,1,3], k = 2
Output
1
Explanation
The reachable ORs are 1 and 3, both one away from 2.

Example 3

Input
nums = [1], k = 10
Output
9

Constraints

  • 1 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000000
  • 1 <= k <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Subarray With Bitwise OR Closest to K — Solution

Find Subarray With Bitwise OR Closest to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find Subarray With Bitwise OR Closest to K is a hard coding problem on arrays, binary search and bit manipulation, asked in Amazon, Google and Meta interviews.

Problem statement

Over all non-empty subarrays of nums, minimise |(bitwise OR of the subarray) - k|.

Return that minimum value.

Example 1

Input: nums = [1,2,4,5], k = 3
Output: 0
Explanation: The subarray [1,2] ORs to exactly 3.

Example 2

Input: nums = [1,3,1,3], k = 2
Output: 1
Explanation: The reachable ORs are 1 and 3, both one away from 2.

Example 3

Input: nums = [1], k = 10
Output: 9

Constraints

  • 1 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000000
  • 1 <= k <= 1000000000

Hints for Find Subarray With Bitwise OR Closest to K

  1. Hint 1

    There are O(n²) subarrays but far fewer distinct ORs — track the ORs of subarrays ending at each index.

  2. Hint 2

    That set has at most about 30 members, because extending leftwards only ever adds bits.

  3. Hint 3

    Evaluate |value - k| for every value the set ever holds.

How to solve Find Subarray With Bitwise OR Closest to K

Fix the right endpoint. The ORs of subarrays ending there form a chain that only gains bits as the window grows leftwards, so at most about 30 distinct values exist per endpoint. Carrying that set forward makes an exhaustive search linear.

Approach

  1. Keep cur, the distinct ORs of subarrays ending at the previous index.
  2. For each new element x, the next set is {x} ∪ {v | x : v in cur}, deduplicated.
  3. Evaluate |value - k| for every value produced and keep the minimum.

Why it works

Every subarray is counted, because each one has a right endpoint and appears in that endpoint's set. The set stays small because along a fixed right endpoint the OR is non-decreasing and every strict increase sets a new bit, of which there are at most 30.

Complexity

  • Time — O(n · 30)
  • Space — O(30)

Pitfalls

  • Skipping the deduplication lets cur grow linearly and the solution becomes O(n²).
  • Forgetting the singleton {x} misses subarrays of length 1.
  • The answer can be 0, so the running minimum must start above any achievable value rather than at 0.

Reference solution

Python

from typing import List

def minimumDifference(nums: List[int], k: int) -> int:
    best = float("inf")
    cur = set()
    for x in nums:
        cur = {x} | {v | x for v in cur}
        for v in cur:
            best = min(best, abs(v - k))
    return int(best)

Java

public static int minimumDifference(int[] nums, int k) {
    long best = Long.MAX_VALUE;
    Set<Integer> cur = new HashSet<>();
    for (int x : nums) {
        Set<Integer> next = new HashSet<>();
        next.add(x);
        for (int v : cur) next.add(v | x);
        cur = next;
        for (int v : cur) best = Math.min(best, Math.abs((long) v - k));
    }
    return (int) best;
}

C++

int minimumDifference(vector<int>& nums, int k) {
    long long best = LLONG_MAX;
    unordered_set<int> cur;
    for (int x : nums) {
        unordered_set<int> next;
        next.insert(x);
        for (int v : cur) next.insert(v | x);
        cur = next;
        for (int v : cur) best = min(best, llabs((long long) v - k));
    }
    return (int) best;
}

JavaScript

var minimumDifference = function(nums, k) {
    var best = Infinity;
    var cur = [];
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        var next = [], seen = {};
        var add = function(v) {
            var s = String(v);
            if (seen[s] !== true) {
                seen[s] = true;
                next.push(v);
                var d = Math.abs(v - k);
                if (d < best) best = d;
            }
        };
        add(x);
        for (var j = 0; j < cur.length; j++) add(cur[j] | x);
        cur = next;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search