Find subarray with bitwise or closest to k

Array Binary Search Bit Manipulation Segment Tree

30.9% acceptance

Feb 24, 2026

205

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. Return the minimum possible value of the absolute difference.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_difference(nums: Vec<i32>, k: i32) -> i32 {
    // Maintain list of distinct OR values for subarrays ending at current position.
    // At most 30 distinct values (one per bit), so O(30 * n) total.
    let mut ans = i32::MAX;
    let mut or_values: Vec<i32> = Vec::new();

    for &x in &nums {
      let mut new_vals: Vec<i32> = vec![x];
      for &v in &or_values {
        let nv = v | x;
        if nv != *new_vals.last().unwrap() {
          new_vals.push(nv);
        }
      }
      or_values = new_vals;
      for &v in &or_values {
        ans = ans.min((k - v).abs());
      }
    }
    ans
  }
}