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)
1import java.util.Arrays;
2
3public class Main {
4 public 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 public static void main(String[] args) {
15 int[] pref = {5, 2, 0, 3, 1};
16 int[] arr = findArray(pref);
17 System.out.println(Arrays.toString(arr));
18 }
19}The Java solution reads the prefix XOR array and constructs the original array by iterating through each element after the first. The solution takes advantage of Java's inherent handling of arrays and clean syntax for processing elements, ensuring clarity and correctness.
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 Java solution is simple and direct, utilizing the XOR operation to restore the original array from the prefix array. The concise logic is powerful and demonstrates how a small change in approach results in equally correct solutions.