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.
- 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 <= 1000001 <= nums[i] <= 10000000001 <= k <= 1000000000
Hints for Find Subarray With Bitwise OR Closest to K
Hint 1
There are
O(n²)subarrays but far fewer distinct ORs — track the ORs of subarrays ending at each index.Hint 2
That set has at most about 30 members, because extending leftwards only ever adds bits.
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
- 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
curgrow linearly and the solution becomesO(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