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)
1#include <stdio.h>
2
3void findArray(int* pref, int n) {
4 int arr[n];
5 arr[0] = pref[0];
6 for(int i = 1; i < n; ++i) {
7 arr[i] = pref[i] ^ pref[i - 1];
8 }
9 for(int i = 0; i < n; ++i) {
10 printf("%d ", arr[i]);
11 }
12 printf("\n");
13}
14
15int main() {
16 int pref[] = {5, 2, 0, 3, 1};
17 int n = sizeof(pref) / sizeof(pref[0]);
18 findArray(pref, n);
19 return 0;
20}This C program first stores the first element in the pref array into the arr array since they are the same. For subsequent elements, it uses the XOR operation with the previous prefix value to deduce the original numbers. The use of a simple loop makes the implementation straightforward.
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#include <vector>
std::vector<int> findOriginalArray(const std::vector<int>& pref) {
int n = pref.size();
std::vector<int> arr(n);
arr[0] = pref[0];
for(int i = 1; i < n; ++i) {
arr[i] = pref[i] ^ pref[i - 1];
}
return arr;
}
int main() {
std::vector<int> pref = {13};
std::vector<int> arr = findOriginalArray(pref);
for(int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}The C++ solution uses direct XOR computation to deduce the original array by applying the XOR operation on consecutive prefix elements. This code emphasizes simplicity while still demonstrating the essential operation needed to revert the prefix operation.