Decode xored permutation

Array Bit Manipulation

66.9% acceptance

Feb 25, 2026

802

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd. It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn decode(encoded: Vec<i32>) -> Vec<i32> {
    let n = encoded.len() + 1;
    // Total XOR of 1..=n
    let total_xor: i32 = (1..=n as i32).fold(0, |acc, x| acc ^ x);
    // XOR of encoded[1], encoded[3], ..., encoded[n-2] = XOR of perm[1..n-1]
    let xor_rest: i32 = encoded.iter().skip(1).step_by(2).fold(0, |acc, &x| acc ^ x);
    let first = total_xor ^ xor_rest;
    let mut perm = vec![first];
    for &e in &encoded {
      perm.push(perm.last().unwrap() ^ e);
    }
    perm
  }
}