Decode xored array

Array Bit Manipulation

87.3% acceptance

Feb 25, 2026

1668

221

There is a hidden integer array arr that consists of n non-negative integers. It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. You are given the encoded array and an integer first, that is the first element of arr. Return the original array arr.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn decode(encoded: Vec<i32>, first: i32) -> Vec<i32> {
    let mut arr = vec![first];
    for &e in &encoded {
      arr.push(arr.last().unwrap() ^ e);
    }
    arr
  }
}