Sponsored
Sponsored
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].
Time Complexity: O(n)
Space Complexity: O(n)
1function findArray(pref) {
2 let arr = [pref[0]];
3 for (let i = 1; i < pref.length; i++) {
4 arr.push(pref[i] ^ pref[i - 1]);
5 }
6 return arr;
7}
8
9const pref = [5, 2, 0, 3, 1];
10const arr = findArray(pref);
11console.log(arr);In this JavaScript function, we utilize an array to keep track of the computed on-the-fly original array. JavaScript's dynamic array operations make the process straightforward, leveraging the functional aspect of JS for easy array manipulation.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1
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));
}
}This C# code reverts the prefix array to its original form using XOR operations. This solution exemplifies simplicity and clarity in using fundamental principles of the XOR operation in C# syntax.