Find Subarray With Bitwise OR Closest to K — Hard Problem & Solution

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

Difficulty: Hard
Topics: Arrays, Binary Search, Bit Manipulation, Segment Tree
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Keep cur, the distinct ORs of subarrays ending at the previous index.
For each new element x, the next set is {x} ∪ {v | x : v in cur}, deduplicated.
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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue