Find The Original Array of Prefix Xor
Find The Original Array of Prefix Xor is a medium bit manipulation problem solved with the xor basics pattern.
The best approach, optimal (xor neighbouring prefixes), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rebuild the running xor each time) up.
Problem
You are given an integer array pref of length n. It was built from some hidden array arr of the same length so that
pref[i] = arr[0] ^ arr[1] ^ … ^ arr[i]
where ^ is bitwise XOR. Recover and return arr. The answer is always unique.
Examples
Example 1
- Input
pref = [6, 3, 3, 10]- Output
[6, 5, 0, 9]- Why
- 6 = 6, 6 ^ 5 = 3, 6 ^ 5 ^ 0 = 3 and 6 ^ 5 ^ 0 ^ 9 = 10.
Example 2
- Input
pref = [12]- Output
[12]- Why
- With one element, the array and its prefix XOR are the same.
Example 3
- Input
pref = [7, 7, 0]- Output
[7, 0, 7]- Why
- 7 ^ 0 = 7 and 7 ^ 0 ^ 7 = 0.
Constraints
1 <= pref.length <= 10^50 <= pref[i] <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (rebuild the running XOR each time) | O(n²) | O(n) |
| Optimal (XOR neighbouring prefixes) | O(n) | O(n) |
1Brute force (rebuild the running XOR each time)
O(n²)The inner loop runs i times for every i.O(n)The output array.Recover the elements left to right. For position i, XOR together all elements already recovered (arr[0..i-1]) from scratch; arr[i] is the value that turns that into pref[i], which is pref[i] XOR that running value.
- For each i from 0 to n - 1, compute x = arr[0] ^ arr[1] ^ … ^ arr[i - 1] with an inner loop (x = 0 when i = 0).
- Set arr[i] = pref[i] ^ x.
- Return arr.
class Solution {
public int[] findArray(int[] pref) {
int n = pref.length;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
int x = 0;
for (int j = 0; j < i; j++) x ^= arr[j];
arr[i] = pref[i] ^ x;
}
return arr;
}
}class Solution:
def findArray(self, pref: List[int]) -> List[int]:
n = len(pref)
arr = [0] * n
for i in range(n):
x = 0
for j in range(i):
x ^= arr[j]
arr[i] = pref[i] ^ x
return arrclass Solution {
public:
vector<int> findArray(vector<int>& pref) {
int n = pref.size();
vector<int> arr(n);
for (int i = 0; i < n; i++) {
int x = 0;
for (int j = 0; j < i; j++) x ^= arr[j];
arr[i] = pref[i] ^ x;
}
return arr;
}
};function findArray(pref) {
const n = pref.length;
const arr = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let x = 0;
for (let j = 0; j < i; j++) x ^= arr[j];
arr[i] = pref[i] ^ x;
}
return arr;
}2Optimal (XOR neighbouring prefixes)
O(n)One XOR per position.O(n)Only the output array (O(1) extra).pref[i - 1] already is the XOR of arr[0..i-1], so there is nothing to recompute. Since pref[i] = pref[i - 1] ^ arr[i], XOR-ing both sides with pref[i - 1] gives arr[i] = pref[i] ^ pref[i - 1].
- arr[0] = pref[0].
- For i from 1 to n - 1, arr[i] = pref[i] ^ pref[i - 1].
- Return arr.
class Solution {
public int[] findArray(int[] pref) {
int n = pref.length;
int[] arr = new int[n];
arr[0] = pref[0];
for (int i = 1; i < n; i++) arr[i] = pref[i] ^ pref[i - 1];
return arr;
}
}class Solution:
def findArray(self, pref: List[int]) -> List[int]:
arr = [pref[0]]
for i in range(1, len(pref)):
arr.append(pref[i] ^ pref[i - 1])
return arrclass Solution {
public:
vector<int> findArray(vector<int>& pref) {
int n = pref.size();
vector<int> arr(n);
arr[0] = pref[0];
for (int i = 1; i < n; i++) arr[i] = pref[i] ^ pref[i - 1];
return arr;
}
};function findArray(pref) {
const arr = [pref[0]];
for (let i = 1; i < pref.length; i++) arr.push(pref[i] ^ pref[i - 1]);
return arr;
}Edge cases to test
- A single element
- Equal neighbouring prefix values, which give a 0 in the answer
- A prefix value of 0, meaning the first i + 1 elements cancel out
Hints
Hint 1
Write down pref[i] and pref[i - 1] as XORs of the original elements. What do they have in common?
Hint 2
XOR-ing a value with itself gives 0, so the shared part cancels.
Hint 3
arr[i] = pref[i] ^ pref[i - 1] for i >= 1, and arr[0] = pref[0].
FAQ
What is the best time complexity for Find The Original Array of Prefix Xor?
Optimal (XOR neighbouring prefixes) runs in O(n) time and O(n) extra space. One XOR per position.
Which pattern does Find The Original Array of Prefix Xor use?
It is a bit manipulation problem that uses the xor basics pattern. Other problems with the same pattern: Swap two numbers, Hamming Distance, Count Paths That Can Form a Palindrome in a Tree.
Is there a brute force solution for Find The Original Array of Prefix Xor?
Yes. Brute force (rebuild the running XOR each time) takes O(n²) time and O(n) space. Recover the elements left to right.
Which edge cases should I test for Find The Original Array of Prefix Xor?
A single element; Equal neighbouring prefix values, which give a 0 in the answer; A prefix value of 0, meaning the first i + 1 elements cancel out.