Decode XORed Array
Easy · Bit Manipulation · Array · Bit Manipulation
Problem
A hidden array arr of n non-negative integers was encoded into an array encoded of length n - 1, where encoded[i] = arr[i] XOR arr[i + 1].
You are given encoded and the integer first, which equals arr[0]. Return the original array arr. The answer always exists and is unique.
Examples
Input: encoded = [6,2,7], first = 3 Output: [3,5,7,0]
3 XOR 6 = 5, 5 XOR 2 = 7 and 7 XOR 7 = 0.
Input: encoded = [1], first = 0 Output: [0,1]
0 XOR 1 gives the second element, 1.
Input: encoded = [0,5,0], first = 4 Output: [4,4,1,1]
An encoded 0 means two equal neighbors: 4, 4, then 4 XOR 5 = 1, 1.
Constraints
- 2 <= n <= 10^4
- encoded.length == n - 1
- 0 <= encoded[i] <= 10^5
- 0 <= first <= 10^5
Approaches
- Baseline: prefix XOR from scratch for each element — time O(n^2), space O(n) for the output
Follow-up
Only one element of arr needs to be known, and it does not have to be the first. The use cases decode backward from the last element, and undo a different encoding, the running XOR of the array.
Related problems
Start free on Cariara · Coding problems · System design studio
