Minimum removals to achieve target xor

Array Dynamic Programming Bit Manipulation

41.5% acceptance

Mar 31, 2026

You are given an integer array nums and an integer target. You may remove any number of elements from nums (possibly zero). Return the minimum number of removals required so that the bitwise XOR of the remaining elements equals target. If it is impossible to achieve target, return -1. The bitwise XOR of an empty array is 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn min_removals(nums: Vec<i32>, target: i32) -> i32 {
    let n = nums.len();
    let total_xor = nums.iter().fold(0, |acc, &x| acc ^ x);
    
    // We want to find a subset to KEEP whose XOR = target.
    // Equivalently, we want to find a subset to REMOVE whose XOR = total_xor ^ target.
    // We want minimum removals, i.e., minimum size subset with XOR = total_xor ^ target.
    // If total_xor == target, answer is 0.
    let remove_xor = total_xor ^ target;
    if remove_xor == 0 {
      return 0;
    }
    
    // n <= 40, so meet-in-the-middle.
    let half = n / 2;
    let left = &nums[..half];
    let right = &nums[half..];
    
    // For each half, enumerate all subsets, storing (xor_value -> min_size).
    fn enumerate(arr: &[i32]) -> HashMap<i32, i32> {
      let mut map = HashMap::new();
      let m = arr.len();
      for mask in 0..(1u64 << m) {
        let mut xor_val = 0;
        let mut cnt = 0;
        for i in 0..m {
          if mask & (1u64 << i) != 0 {
            xor_val ^= arr[i];
            cnt += 1;
          }
        }
        let entry = map.entry(xor_val).or_insert(cnt);
        if cnt < *entry {
          *entry = cnt;
        }
      }
      map
    }
    
    let left_map = enumerate(left);
    let right_map = enumerate(right);
    
    let mut ans = i32::MAX;
    for (&lx, &lc) in &left_map {
      let need = lx ^ remove_xor;
      if let Some(&rc) = right_map.get(&need) {
        let total = lc + rc;
        if total > 0 && total < ans {
          ans = total;
        }
      }
    }
    
    if ans == i32::MAX { -1 } else { ans }
  }
}