Find Subarray With Bitwise OR Closest to K
HardPrompt
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 <= 1051 <= nums[i] <= 1091 <= k <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
min_diffto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through the array with an index
lfrom0ton-1(representing the start of the subarray). - Inside this loop, initialize
current_or = 0. - Start a nested loop with an index
rfromlton-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_diffholds the result.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Initialize
min_difftoInteger.MAX_VALUE. - Initialize an empty set,
prev_ors, to store distinct OR values of subarrays ending at the previous index. - Iterate through each
numin thenumsarray. - Create a new empty set,
current_ors. - Add
numtocurrent_ors. - For each
or_valinprev_ors, addor_val | numtocurrent_ors. - For each
valincurrent_ors, updatemin_diff = Math.min(min_diff, Math.abs(val - k)). - Set
prev_ors = current_orsto prepare for the next iteration. - Return
min_diff.
Walkthrough
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:
- The value
nums[i]itself (for the subarray[i,i]). - The values
val | nums[i]for everyvalinprev_ors. As we compute the values forcurrent_ors, we also update our globalmin_diffby comparing each new OR value withk. After processing indexi,current_orsbecomesprev_orsfor 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.
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.