✅Super Easy Bit Manipulation (C++/Java/Python) Solution With Detailed Explanation✅
Intuition\nThe algorithm reconstructs an original array from its prefix XOR array by iteratively computing each element as the XOR of the cumulative XOR up to t
# Intuition\nThe algorithm reconstructs an original array from its prefix XOR array by iteratively computing each element as the XOR of the cumulative XOR up to the previous element and the current element of the prefix XOR array.\n\n# Approach\n\n1. **Initialization**: An integer `n` is initialized to store the size of the input prefix XOR array `pref`. A new vector `res` of size `n` is created to store the result, i.e., the original array.\n\n2. **Cumulative XOR Calculation**: An integer `x` is initialized to 0. This variable will hold the cumulative XOR of elements as they are added to the `res` array. It effectively represents the prefix XOR up to the previous element of the array being reconstructed.\n\n3. **Reconstruction Loop**:\n   - The loop iterates over each index `i` of the `pref` array.\n   - For each index `i`, the value of `res[i]` is determined by XORing `x` with `pref[i]`. Since `x` holds the XOR of all previous elements of the resulting array, XORing it with `pref[i]` effectively reverses the prefix XOR operation, yielding the original value at `res[i]`.\n   - After calculating `res[i]`, `x` is updated by XORing it with `res[i]`, thus including the latest element in the cumulative XOR for the next iteration.\n\n4. **Return Result**: After the loop completes, the `res` vector, which now contains the original array, is returned.\n\n### Complexity Analysis\n\n- **Time Complexity**: The algorithm iterates once over the array `pref`, performing a constant number of operations for each element (specifically, two XOR operations and a couple of assignments). Therefore, the time complexity is `O(n)`, where `n` is the length of the input array `pref`.\n\n- **Space Complexity**: The space complexity is also `O(n)` due to the storage requirements of the `res` vector, which is the same size as the input array `pref`. The rest of the variables (`n` and `x`) use constant space.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<int> findArray(vector<int>& pref) {\n        int n = pref.size();\n        vector<int> res (n);\n        int x = 0;\n        for (int i=0; i<n; i++)\n        {\n            res[i] = x ^ pref[i];\n            x ^= res[i];\n        }\n\n        return res;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public int[] findArray(int[] pref) {\n        int n = pref.length;\n        int[] res = new int[n];\n        int x = 0;\n        for (int i = 0; i < n; i++) {\n            res[i] = x ^ pref[i];\n            x ^= res[i];\n        }\n        return res;\n    }\n}\n\n```\n```Python []\nfrom typing import List\n\nclass Solution:\n    def findArray(self, pref: List[int]) -> List[int]:\n        n = len(pref)\n        res = [0] * n\n        x = 0\n        for i in range(n):\n            res[i] = x ^ pref[i]\n            x ^= res[i]\n        \n        return res\n\n```
['Bit Manipulation', 'C++', 'Java', 'Python3']