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)
1using System;
2
3class Program {
4 static int[] FindArray(int[] pref) {
5 int n = pref.Length;
6 int[] arr = new int[n];
7 arr[0] = pref[0];
8 for (int i = 1; i < n; i++) {
9 arr[i] = pref[i] ^ pref[i - 1];
10 }
11 return arr;
12 }
13
14 static void Main() {
15 int[] pref = {5, 2, 0, 3, 1};
16 int[] arr = FindArray(pref);
17 Console.WriteLine(string.Join(" ", arr));
18 }
19}This C# program defines a method to find the original array using the prefix XOR operations. It explicitly handles arrays and iterates over each element, showcasing C#'s array capabilities and control structures.
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
This JavaScript function effectively reverses the prefix process using direct computation of each array element through XOR traversal. The compact and readable code highlights JavaScript's efficiency in array handling tasks.