Find a value of a mysterious function closest to target

Array Binary Search Bit Manipulation Segment Tree

47.0% acceptance

Feb 25, 2026

404

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible. Return the minimum possible value of |func(arr, l, r) - target|. Notice that func should be called with the values l and r where 0 <= l, r < arr.length. func(arr, l, r) = arr[l] & arr[l+1] & ... & arr[r]

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn closest_to_target(arr: Vec<i32>, target: i32) -> i32 {
    let mut ans = i32::MAX;
    // cur: list of (and_value) - distinct AND values of subarrays ending at i
    let mut cur: Vec<i32> = Vec::new();
    for &x in &arr {
      // New subarrays: extend all previous + the single element x
      let mut next: Vec<i32> = vec![x];
      for v in &cur {
        let nv = v & x;
        if next.last() != Some(&nv) {
          next.push(nv);
        }
      }
      // next is in non-increasing order (since AND can only decrease or stay)
      // Deduplicate while maintaining order
      next.dedup();
      for &v in &next {
        ans = ans.min((v - target).abs());
      }
      cur = next;
    }
    ans
  }
}