Medium

Find The Original Array of Prefix Xor

LAB

Given prefix xor values, return the original array that produced them.

EXAMPLES

Example 1

Input
{
  "pref": [
    5,
    2,
    0,
    3,
    1
  ]
}

Output
[
  5,
  7,
  2,
  3,
  2
]

FUNCTION SHAPE

pref: intArray→intArray

SOLUTION NOTE

Reverse the prefix XOR operation. Since XOR is its own inverse: arr[i] = pref[i] ^ pref[i-1]. The key insight is that a ^ a = 0, so XORing consecutive prefix values cancels all elements except arr[i].

Reveal reference solution +

pythonREFERENCE

def findArray(self, pref: List[int]) -> List[int]:
    # arr[i] = pref[i] ^ pref[i-1]
    # Because: pref[i] ^ pref[i-1] = (arr[0]^...^arr[i]) ^ (arr[0]^...^arr[i-1])
    #                              = arr[i]  (all others cancel out)

    for i in range(len(pref) - 1, 0, -1):
        pref[i] = pref[i] ^ pref[i - 1]
    return pref

TimeO(n)

SpaceO(1)

Open on LeetCode ↗