✅ 92.93% One Line XORing
Intuition\nUpon reading the problem, the first thing that might come to mind is how the XOR operation behaves. Since the prefix XOR array is essentially an accu
# Intuition\nUpon reading the problem, the first thing that might come to mind is how the XOR operation behaves. Since the prefix XOR array is essentially an accumulation of XOR operations, the inverse process would involve \'undoing\' the XOR operation. We remember that XOR has the following properties:\n\n1. $ a \\oplus a = 0 $\n2. $ a \\oplus 0 = a $\n3. XOR operation is both associative and commutative.\n\nThese properties hint towards the approach of using previous prefix values to deduce the current value.\n\n## Live Coding in Python & Go?\nhttps://youtu.be/nyRgqGYnAf4?si=8YeN7ukMB6uEdXSi\n\n# Approach\n1. The first observation is that the first element of the original array is equal to the first element of the prefix array. This is because there\'s no prior value to XOR with.\n2. For every subsequent element in the prefix array, we can obtain the corresponding element in the original array by XORing the current prefix value with the previous prefix value. This is derived from the properties of XOR, which allows us to \'cancel out\' values, essentially \'undoing\' the accumulation.\n\nUsing this approach, we iterate through the prefix array and populate our original array.\n\n# Complexity\n- Time complexity: $O(n)$\n  - We iterate through the prefix array exactly once, resulting in a linear time complexity.\n\n- Space complexity: $O(n)$\n  - We are creating a new list that has the same size as the input prefix array, resulting in a linear space complexity.\n\n# Code\n```python []\nclass Solution:\n    def findArray(self, pref: List[int]) -> List[int]:\n        return [pref[0]] + [pref[i] ^ pref[i-1] for i in range(1, len(pref))]\n```\n``` Java []\npublic class Solution {\n    public int[] findArray(int[] pref) {\n        int[] result = new int[pref.length];\n        result[0] = pref[0];\n        for(int i = 1; i < pref.length; i++) {\n            result[i] = pref[i] ^ pref[i-1];\n        }\n        return result;\n    }\n}\n```\n``` Go []\nfunc findArray(pref []int) []int {\n    result := make([]int, len(pref))\n    result[0] = pref[0]\n    for i := 1; i < len(pref); i++ {\n        result[i] = pref[i] ^ pref[i-1]\n    }\n    return result\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn find_array(pref: Vec<i32>) -> Vec<i32> {\n        let mut result = Vec::with_capacity(pref.len());\n        result.push(pref[0]);\n        for i in 1..pref.len() {\n            result.push(pref[i] ^ pref[i-1]);\n        }\n        result\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<int> findArray(vector<int>& pref) {\n        vector<int> result(pref.size());\n        result[0] = pref[0];\n        for(int i = 1; i < pref.size(); i++) {\n            result[i] = pref[i] ^ pref[i-1];\n        }\n        return result;\n    }\n};\n```\n``` C# []\npublic class Solution {\n    public int[] FindArray(int[] pref) {\n        int[] result = new int[pref.Length];\n        result[0] = pref[0];\n        for(int i = 1; i < pref.Length; i++) {\n            result[i] = pref[i] ^ pref[i-1];\n        }\n        return result;\n    }\n}\n```\n``` JavaScript []\nvar findArray = function(pref) {\n        let result = [pref[0]];\n        for(let i = 1; i < pref.length; i++) {\n            result.push(pref[i] ^ pref[i-1]);\n        }\n        return result;\n    }\n```\n``` PHP []\nclass Solution {\n    function findArray($pref) {\n        $result = [];\n        $result[] = $pref[0];\n        for($i = 1; $i < count($pref); $i++) {\n            $result[] = $pref[$i] ^ $pref[$i-1];\n        }\n        return $result;\n    }\n}\n```\n\n---\n\n## Performance\n\n| Language   | Execution Time (ms) | Memory Usage (MB) |\n|------------|---------------------|-------------------|\n| Java       | 1                   | 58.4              |\n| Rust       | 39                  | 3.5               |\n| Go         | 85                  | 9.6               |\n| C++        | 86                  | 76.3              |\n| JavaScript | 184                 | 71.2              |\n| C#         | 243                 | 60.2              |\n| PHP        | 253                 | 39.4              |\n| Python3    | 655                 | 36.5              |\n\n![s1.png](https://assets.leetcode.com/users/images/a51a88af-5d72-4a10-8f49-6198d913dcb2_1698712529.1288717.png)\n\n\n## What We Have Learned?\n\nFrom this problem, we\'ve reinforced our understanding of the XOR operation and its properties, particularly how it can be used to deduce information from accumulated data. The solution is optimal because it utilizes the inherent properties of XOR to deduce the original values in a single pass through the prefix array. The approach is both space and time efficient, and showcases how sometimes, understanding the underlying mathematics or logic (in this case, bitwise operations) can lead to very efficient solutions.
['Array', 'Bit Manipulation', 'PHP', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']