LeetCode 3171 - Find Subarray With Bitwise OR Closest to K

The problem asks us to find a subarray within a given array nums such that the absolute difference between the integer k and the bitwise OR of the subarray elements is minimized.

leetcodehardarraybinary-searchbit-manipulationsegment-tree

LeetCode Problem 3171

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Bit Manipulation, Segment Tree

Solution

Problem Understanding

The problem asks us to find a subarray within a given array nums such that the absolute difference between the integer k and the bitwise OR of the subarray elements is minimized. A subarray is any contiguous sequence of elements in the array, so we are looking for a segment of nums where applying the bitwise OR to all elements in that segment produces a value closest to k.

The input consists of an array nums of size up to $10^5$ and integers in the range $1$ to $10^9$. The target value k also falls within $1$ to $10^9$. The constraints suggest that a naive brute-force approach that checks all subarrays would be too slow because there can be $O(n^2)$ subarrays, which is prohibitive for $n = 10^5$.

Edge cases include arrays of length 1, cases where all elements are larger than k, or when a perfect match exists in a single element or small subarray. The problem guarantees that the array is non-empty, so we do not need to handle an empty array.

The key challenge is computing the OR of all subarrays efficiently and finding the one closest to k without explicitly generating every subarray.

Approaches

The brute-force approach would iterate through all possible subarrays of nums. For each subarray, we compute the OR of its elements and then calculate the absolute difference from k. We track the minimum difference encountered. This approach is correct because it considers every possible subarray, but it is too slow with time complexity $O(n^2 \cdot \text{bitwidth})$ or worse.

The optimal approach leverages two key observations about the bitwise OR operation. First, OR is monotonic when extending a subarray to the right; adding more elements can only turn more bits to 1 and never resets bits to 0. Second, the number of distinct OR results we can obtain from subarrays ending at a specific index is limited to $O(\log(\text{max num}))$, since each new bit can only be set once. Using these observations, we can iteratively maintain all possible OR values ending at the current index and merge them efficiently with the OR of the current number. This allows us to compute all reachable OR values without checking all subarrays explicitly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Checks all subarrays; too slow for large n
Optimal O(n * log(max(nums))) O(log(max(nums))) Maintains reachable ORs efficiently to compute minimal difference

Algorithm Walkthrough

  1. Initialize a variable res to inf to store the minimum absolute difference found so far. Also, initialize a set prev to store OR results of subarrays ending at the previous index, starting empty.
  2. Iterate through each number num in nums.
  3. For the current number, generate a new set curr by taking the OR of num with every element in prev. This produces all possible OR values for subarrays ending at this index. Add num itself to curr to account for subarrays of length 1.
  4. For each OR value in curr, compute the absolute difference from k and update res if the difference is smaller.
  5. Update prev to curr for the next iteration.
  6. After processing all numbers, return res as the minimum absolute difference.

Why it works: By keeping track of all possible OR values of subarrays ending at each index, we ensure we do not miss any subarray. Since the number of distinct OR values at any step is limited to the number of bits in the largest number (at most 30 for numbers ≤ $10^9$), this approach is efficient. The monotonic property of OR guarantees that extending subarrays only adds new bits, so our set prev correctly propagates all reachable OR values.

Python Solution

from typing import List

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        res = float('inf')
        prev = set()
        for num in nums:
            curr = {num}
            for val in prev:
                curr.add(val | num)
            for val in curr:
                res = min(res, abs(val - k))
            prev = curr
        return res

The code initializes res to infinity and uses a set prev to store OR values ending at the previous index. For each number, we compute all OR values ending at the current index by combining it with prev and including the number itself. We then update the minimum absolute difference for all current OR values. The set prev is updated for the next iteration.

Go Solution

func minimumDifference(nums []int, k int) int {
    res := int(1e18)
    prev := make(map[int]struct{})
    
    for _, num := range nums {
        curr := make(map[int]struct{})
        curr[num] = struct{}{}
        for val := range prev {
            curr[val | num] = struct{}{}
        }
        for val := range curr {
            diff := val - k
            if diff < 0 {
                diff = -diff
            }
            if diff < res {
                res = diff
            }
        }
        prev = curr
    }
    
    return res
}

The Go version uses a map[int]struct{} to mimic a set of OR values. It follows the same logic: compute all new OR values, update the minimum difference, and propagate curr as prev for the next iteration.

Worked Examples

Example 1: nums = [1,2,4,5], k = 3

Step by step:

Index num prev ORs curr ORs min diff
0 1 {} {1}
1 2 {1} {2, 3}
2 4 {2,3} {4,6,7} min(
3 5 {4,6,7} {5,7,6,7} min(

Example 2: nums = [1,3,1,3], k = 2

Step by step:

Index num prev ORs curr ORs min diff
0 1 {} {1}
1 3 {1} {3,3} min(
2 1 {3} {3,1} min(
3 3 {3,1} {3,1,3} min(

Example 3: nums = [1], k = 10

Only one subarray [1] → OR=1 → |10-1|=9 → result=9

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(max(nums))) Each number generates at most 30 OR values (number of bits in 10^9). Iterating through all numbers gives n * 30.
Space O(log(max(nums))) We maintain a set of OR values at each step, which is bounded by the number of bits in the largest number.

The logarithmic factor arises from the bitwise nature of OR. Since each bit can only be set once in the propagation of ORs across a subarray, the number of distinct ORs remains small even for large arrays.

Test Cases

# Provided examples
assert Solution().minimumDifference([1,2,4,5], 3) == 0  # Subarray [1,2]
assert Solution().minimumDifference([1,3,1,3], 2) == 1  # Subarray [1] or [3]
assert Solution().minimumDifference([1], 10) == 9       # Single element

# Edge cases
assert Solution().minimumDifference([10**9], 1) == 999999999  # Single large number
assert Solution().minimumDifference([1,1,1,1], 2) == 1        # All numbers smaller than k
assert Solution().minimumDifference([1,2,4,8], 15) == 0       # Full array OR equals k
assert Solution().minimumDifference([8,4,2,1], 7) == 0