Scale Engineer

Find Subarray With Bitwise OR Closest to K

Hard
#2817Time: 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).
Patterns
Bit Manipulation
Algorithms
Binary Search
Data structures
ArraySegment Tree

Prompt

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= 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_diff to a very large value (e.g., Integer.MAX_VALUE).
  • Iterate through the array with an index l from 0 to n-1 (representing the start of the subarray).
  • Inside this loop, initialize current_or = 0.
  • Start a nested loop with an index r from l to n-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_diff holds 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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem