Find The Original Array Of Prefix Xor - Leetcode Solution

The problem statement for the Find The Original Array of Prefix XOR problem on LeetCode is as follows:

Given an array XOR[] where XOR[0] = arr[0] and XOR[i] = arr[i] XOR XOR[i-1] for i > 0, find a possible original array arr of size n from XOR[] – any array such that XOR[] is equal to the prefix XOR of arr.

In this problem, we are given an array XOR[] where the first element is the same as the input array arr and each subsequent element is equal to the XOR of the current element in the input array and the previous element in the XOR array. The task is to find the original array arr that would lead to the given XOR array.

To solve this problem, we will make use of a simple observation:

• The XOR operation is its own inverse operation. This means that if we XOR two values together and then XOR the result with one of the values, we will get the other value as the result.

Using this observation, we can find the original array arr by iterating over the XOR array and performing the XOR operation with the previous element of the array to get the current element of the original array. At the first index of the XOR array, we simply add the value of the first element of the original array to the result.

Let's walk through an example:

Input: XOR[] = [6, 2, 4, 8] Output: arr[] = [6, 4, 6, 14]

Step 1: Initialize the first element of the original array as the first element of the XOR array. arr[0] = XOR[0] = 6

Step 2: Iterate over the remainder of the XOR array and calculate the current element of the original array using the XOR operation. For i = 1, arr[1] = XOR[1] XOR arr[0] = 2 XOR 6 = 4 For i = 2, arr[2] = XOR[2] XOR arr[1] = 4 XOR 4 = 6 For i = 3, arr[3] = XOR[3] XOR arr[2] = 8 XOR 6 = 14

Step 3: Return the resulting original array. arr[] = [6, 4, 6, 14]

The time complexity of this algorithm is O(n) as we iterate over the input array once to calculate the original array. The space complexity is also O(n) as we need to store the original array as we calculate its elements.

1