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 <iostream>
2#include <vector>
3
4std::vector<int> findArray(const std::vector<int>& pref) {
5 int n = pref.size();
6 std::vector<int> arr(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
14int main() {
15 std::vector<int> pref = {5, 2, 0, 3, 1};
16 std::vector<int> arr = findArray(pref);
17 for(int num : arr) {
18 std::cout << num << " ";
19 }
20 std::cout << std::endl;
21 return 0;
22}The C++ solution utilizes a vector to store and process input, making use of a for-loop to rebuild the original array by applying XOR to successive elements of the prefix array. The solution is efficient, and the use of vectors demonstrates modern C++ practices.
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 C solution reflects the direct calculation of the original array using XOR directly on the prefix elements. Using principles similar to other approaches, this code shows how directly the computation can be managed given the XOR properties.