Maximum xor for each query

Array Bit Manipulation Prefix Sum

84.8% acceptance

Feb 25, 2026

1263

194

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times: Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith query. Remove the last element from the current array nums. Return an array answer, where answer[i] is the answer to the ith query.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_maximum_xor(nums: Vec<i32>, maximum_bit: i32) -> Vec<i32> {
    let mask = (1 << maximum_bit) - 1;
    let mut xor_all = nums.iter().fold(0i32, |acc, &x| acc ^ x);
    let mut result = Vec::with_capacity(nums.len());
    for i in (0..nums.len()).rev() {
      result.push(xor_all ^ mask);
      xor_all ^= nums[i];
    }
    result
  }
}