Vultr DocsLatest Content

Find The Original Array of Prefix Xor

Updated on 28 May, 2025
Find The Original Array of Prefix Xor header image

Problem Statement

Given an integer array pref with size n, the task is to determine another integer array arr also of size n, such that for each index i in arr, the prefix sum of elements from the start of the array up to i computed using the bitwise XOR operation matches the i-th entry in pref. Specifically, the requirement is to have: [ \text{pref}[i] = \text{arr}[0] \oplus \text{arr}[1] \oplus \ldots \oplus \text{arr}[i] ] where ( \oplus ) denotes the bitwise XOR operator. Importantly, it is guaranteed that the configuration ensuring this is unique.

Examples

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 <= 105
  • 0 <= pref[i] <= 106

Approach and Intuition

To reconstruct the array arr from the given prefix XOR sums pref, each element of arr can be inferred separately by utilizing properties of the XOR operation, especially considering its reversibility (i.e., ( a \oplus a = 0 ) and ( a \oplus 0 = a )):

  1. Initialize arr[0] as pref[0] because the first element in pref is derived solely by XOR-ing arr[0] with no preceding elements:

    [ \text{arr}[0] = \text{pref}[0] ]

  2. For every subsequent element i from 1 to n-1 in arr, determine arr[i] using the difference in concurrent entries in the pref array:

    [ \text{arr}[i] = \text{pref}[i-1] \oplus \text{pref}[i] ]

    Here,

    • pref[i] computes the cumulative XOR from the start up to i, i.e., ( \text{arr}[0] \oplus \ldots \oplus \text{arr}[i] )
    • pref[i-1] gives the cumulative XOR up to i-1

    XOR-ing pref[i] with pref[i-1] cancels out all terms except arr[i], utilizing the property ( a \oplus a = 0 ) and ( a \oplus 0 = a ).

Each element in arr is thereby iteratively solved for in linear time by processing the pref array from the first to last element applying the above steps. This simple yet effective linear iterative approach follows from understanding and utilizing the properties of the XOR operation and matches the constraints perfectly, ensuring a solution in O(n) complexity.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    vector<int> decodePrefixXOR(vector<int>& prefix) {
        int length = prefix.size();
        
        for (int i = length - 1; i > 0; i--) {
            prefix[i] = prefix[i] ^ prefix[i - 1];
        }
        
        return prefix;
    }
};

The given C++ code solves the problem of reconstructing the original array from a given array that represents the prefix XOR values. The approach utilized by the code is based on the properties of XOR, specifically that (XOR(XOR(a, b), b) = a).

Here's the process followed in the solution:

  1. Determine the length of the prefix vector which contains the prefix XOR values.
  2. Iterate backwards through the prefix vector starting from the last element. This backward iteration is crucial as each element is the result of the XOR operation applied sequentially from the start of the array.
  3. For each element in the array (starting from the last and moving to the first), update the current element by performing the XOR operation with the previous element. This is done using the formula prefix[i] = prefix[i] ^ prefix[i - 1].
  4. The loop skips the first element of the array because its value is already the desired value as there is no preceding element to XOR with.

Once the iteration is complete, the prefix array itself is modified in place to represent the original array and is returned.

This solution is efficient with a time complexity of O(n), where n is the number of elements in the prefix array. This is because the solution only requires one pass through the array from the last element to the first, updating each element accordingly. The approach leverages the XOR operation's properties effectively to reverse the prefix sum process.

java 
class Solution {
    public int[] reconstructArray(int[] array) {
        int size = array.length;

        for (int j = size - 1; j > 0; j--) {
            array[j] = array[j] ^ array[j - 1];
        }

        return array;
    }
}

The solution aims to find the original array from a given array containing prefix XOR values. The code is implemented in Java, following a reverse iteration approach to reconstruct the original array values.

Follow this step-by-step breakdown of how the solution operates:

  1. Declare a class named Solution with a public method reconstructArray, which takes an integer array as an input.
  2. The method first retrieves the length of the input array and stores it in the variable size.
  3. Using a for-loop, iterate from the end of the array to its beginning, reversing the prefix XOR computation:
    • Each element of the array gets updated by applying the XOR operation between the current element and its predecessor.
  4. After completing the loop, the method returns the modified array, which now represents the original data before the prefix XORs were applied.

This solution effectively reverses the prefix XOR operation to retrieve the initial array configuration by leveraging XOR properties.

Comments

No comments yet.