2433. Find The Original Array of Prefix Xor Solution

The problem

You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].

Note that ^ denotes the bitwise-xor operation.

It can be proven that the answer is unique.

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

Constraints:

1 <= pref.length <= 10⁵
0 <= pref[i] <= 10⁶

Approach overview

Problem Overview: You are given an array pref where pref[i] represents the XOR of all elements from index 0 to i in the original array. Your task is to reconstruct the original array that produced this prefix XOR sequence.

The key observation comes from XOR properties. If pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i], then XORing two consecutive prefix values cancels the common part. This allows you to isolate each element of the original array.

Approach 1: Iterative Approach (O(n) time, O(1) space)

Create the result array and compute elements sequentially. The first element is straightforward: arr[0] = pref[0]. For every index i > 0, the previous prefix contains arr[0] ^ ... ^ arr[i-1]. XORing pref[i] with pref[i-1] cancels that shared portion and leaves only arr[i]. Iterate through the array once and apply this operation to recover each value.

This approach works because XOR has two useful properties: a ^ a = 0 and a ^ 0 = a. When you compute pref[i] ^ pref[i-1], all earlier elements cancel out. The algorithm requires only a single pass through the array and constant extra memory.

Approach 2: Prefix XOR Direct Computation (O(n) time, O(1) space)

This method uses the same mathematical relationship but frames it directly from the prefix XOR definition. The original array satisfies: arr[i] = pref[i] ^ pref[i-1]. Initialize the first element from the prefix array, then compute each subsequent element using this formula.

Instead of maintaining additional structures, you simply read the current and previous prefix values. The algorithm performs one XOR operation per element, making it extremely efficient. This approach is common in problems involving bit manipulation and prefix transformations on an array.

Recommended for interviews: The direct prefix XOR computation is the expected solution. Interviewers want to see that you recognize how prefix XOR works and apply the identity pref[i] ^ pref[i-1]. Mentioning the XOR cancellation property demonstrates a solid understanding of bit manipulation. A brute-force reconstruction would be unnecessary here, while the O(n) prefix-based approach shows you understand both the math and the implementation.

Approach 1: Iterative Approach

This approach involves iterating through the prefix XOR array and using the properties of XOR to deduce the original array. Starting from the first element, which is the same as in the original array, subsequent elements can be found using the formula:

arr[i] = pref[i] ^ pref[i-1]

since pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i] and pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1].

Python

def findArray(pref):
    arr = [pref[0]]
    for i in range(1, len(pref)):
        arr.append(pref[i] ^ pref[i - 1])
    return arr

pref = [5, 2, 0, 3, 1]
arr = findArray(pref)
print(arr)

Java

import java.util.Arrays;

public class Main {
    public static 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;
    }

    public static void main(String[] args) {
        int[] pref = {5, 2, 0, 3, 1};
        int[] arr = findArray(pref);
        System.out.println(Arrays.toString(arr));
    }
}

C++

#include <iostream>
#include <vector>

std::vector<int> findArray(const std::vector<int>& pref) {
    int n = pref.size();
    std::vector<int> arr(n);
    arr[0] = pref[0];
    for(int i = 1; i < n; ++i) {
        arr[i] = pref[i] ^ pref[i - 1];
    }
    return arr;
}

int main() {
    std::vector<int> pref = {5, 2, 0, 3, 1};
    std::vector<int> arr = findArray(pref);
    for(int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

JavaScript

function findArray(pref) {
    let arr = [pref[0]];
    for (let i = 1; i < pref.length; i++) {
        arr.push(pref[i] ^ pref[i - 1]);
    }
    return arr;
}

const pref = [5, 2, 0, 3, 1];
const arr = findArray(pref);
console.log(arr);

#include <stdio.h>

void findArray(int* pref, int n) {
    int arr[n];
    arr[0] = pref[0];
    for(int i = 1; i < n; ++i) {
        arr[i] = pref[i] ^ pref[i - 1];
    }
    for(int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int pref[] = {5, 2, 0, 3, 1};
    int n = sizeof(pref) / sizeof(pref[0]);
    findArray(pref, n);
    return 0;
}

using System;

class Program {
    static 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;
    }

    static void Main() {
        int[] pref = {5, 2, 0, 3, 1};
        int[] arr = FindArray(pref);
        Console.WriteLine(string.Join(" ", arr));
    }
}

Utilizing Python's list operations, this solution iteratively applies XOR on consecutive elements of the prefix array to derive the original array elements. The usage of Python's simple iteration and list manipulation makes the solution concise and readable.

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor

Approach 2: Prefix XOR Direct Computation

This approach calculates each element of the original array directly by using the property of XOR that makes it its own inverse. By understanding that the difference between consecutive prefix values gives the desired element, this method is implemented in a direct computational manner.

Python

def findOriginalArray(pref):
    arr = [pref[0]]
    for i in range(1, len(pref)):
        arr.append(pref[i] ^ pref[i - 1])
    return arr

pref = [13]
arr = findOriginalArray(pref)
print(arr)

Java

import java.util.Arrays;

public class MainAlternate {
    public static int[] findOriginalArray(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;
    }

    public static void main(String[] args) {
        int[] pref = {13};
        int[] arr = findOriginalArray(pref);
        System.out.println(Arrays.toString(arr));
    }
}

C++

#include <iostream>
#include <vector>

std::vector<int> findOriginalArray(const std::vector<int>& pref) {
    int n = pref.size();
    std::vector<int> arr(n);
    arr[0] = pref[0];
    for(int i = 1; i < n; ++i) {
        arr[i] = pref[i] ^ pref[i - 1];
    }
    return arr;
}

int main() {
    std::vector<int> pref = {13};
    std::vector<int> arr = findOriginalArray(pref);
    for(int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

JavaScript

function findOriginalArray(pref) {
    let arr = [pref[0]];
    for (let i = 1; i < pref.length; i++) {
        arr.push(pref[i] ^ pref[i - 1]);
    }
    return arr;
}

const pref = [13];
const arr = findOriginalArray(pref);
console.log(arr);

#include <stdio.h>

void findOriginalArray(int* pref, int n) {
    int arr[n];
    arr[0] = pref[0];
    for(int i = 1; i < n; ++i) {
        arr[i] = pref[i] ^ pref[i - 1];
    }
    for(int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int pref[] = {13};
    int n = sizeof(pref) / sizeof(pref[0]);
    findOriginalArray(pref, n);
    return 0;
}

using System;

class ProgramDirect {
    static int[] FindOriginalArray(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;
    }

    static void Main() {
        int[] pref = {13};
        int[] arr = FindOriginalArray(pref);
        Console.WriteLine(string.Join(" ", arr));
    }
}

In this Python version, we compute the original array by realizing that each element after the first is the XOR of consecutive prefix elements. This concise function demonstrates Python's capabilities of handling such operations efficiently in a compact form.

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor

Approach 3: Bit Manipulation

According to the problem statement, we have equation one:

$pref[i]=arr[0] \oplus arr[1] \oplus cdots \oplus arr[i]

So, we also have equation two:

pref[i-1]=arr[0] \oplus arr[1] \oplus cdots \oplus arr[i-1]

We perform a bitwise XOR operation on equations one and two, and get:

pref[i] \oplus pref[i-1]=arr[i]

That is, each item in the answer array is obtained by performing a bitwise XOR operation on the adjacent two items in the prefix XOR array.

The time complexity is O(n), where n is the length of the prefix XOR array. Ignoring the space consumption of the answer, the space complexity is O(1)$.

TypeScript

function findArray(pref: number[]): number[] {
    let ans = pref.slice();
    for (let i = 1; i < pref.length; i++) {
        ans[i] = pref[i - 1] ^ pref[i];
    }
    return ans;
}

func findArray(pref []int) []int {
	n := len(pref)
	ans := []int{pref[0]}
	for i := 1; i < n; i++ {
		ans = append(ans, pref[i-1]^pref[i])
	}
	return ans
}

Rust

impl Solution {
    pub fn find_array(pref: Vec<i32>) -> Vec<i32> {
        let n = pref.len();
        let mut res = vec![0; n];
        res[0] = pref[0];
        for i in 1..n {
            res[i] = pref[i] ^ pref[i - 1];
        }
        res
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Approach	Time Complexity: O(n) Space Complexity: O(n)
Prefix XOR Direct Computation	Time Complexity: O(n) Space Complexity: O(n)
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Approach	O(n)	O(1)	General case when reconstructing the array sequentially from prefix values
Prefix XOR Direct Computation	O(n)	O(1)	Best approach when leveraging XOR cancellation between consecutive prefix values

Frequently asked questions

Is Find The Original Array of Prefix Xor easy or hard?

The problem is rated Medium on LeetCode but is conceptually straightforward once you recognize the XOR prefix property. Understanding how XOR cancels identical values makes the reconstruction step immediate.

Find The Original Array of Prefix Xor Python/Java solution

In Python or Java, iterate through the prefix array and compute arr[i] = pref[i] ^ pref[i-1] for i > 0, with arr[0] = pref[0]. This implementation takes O(n) time and constant extra space and works identically across languages.

How to solve Find The Original Array of Prefix Xor in O(n)?

Start with arr[0] = pref[0]. For every index i greater than 0, compute arr[i] = pref[i] ^ pref[i-1]. XORing consecutive prefix values removes the common prefix portion and isolates the current element, allowing reconstruction in a single linear scan.

What is the best approach for Find The Original Array of Prefix Xor?

The best approach uses the XOR cancellation property. If pref[i] represents the XOR from index 0 to i, then the original value can be recovered with arr[i] = pref[i] ^ pref[i-1]. This produces the array in O(n) time and O(1) extra space with a single pass.

Is Find The Original Array of Prefix Xor asked at Google/Amazon/Meta?

Problems involving prefix XOR and bit manipulation appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the concept of reversing prefix operations and applying XOR properties is a common interview pattern.

What data structure is used in Find The Original Array of Prefix Xor?

The solution primarily works with arrays and uses bit manipulation through XOR operations. No additional data structures such as hash maps or stacks are required because the prefix relationship directly reveals each element.

What is the time complexity of Find The Original Array of Prefix Xor?

The optimal solution runs in O(n) time because each element is computed exactly once. Only one XOR operation per index is required. Space complexity is O(1) excluding the output array since no additional data structures are needed.

Find The Original Array of Prefix Xor solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Prefix XOR Direct Computation

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find The Original Array of Prefix Xor solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Prefix XOR Direct Computation

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems