✅ Beats 99.24% 🔥 || 3 Approaches 💡 ||
Approach 1: Prefix Sum\n\n\n\n# Intuition:\n\nIf we have an array of prefix sums pref, then the original array arr can be recovered by taking the prefix sum of 
# Approach 1: Prefix Sum\n\n![Screenshot 2023-10-31 at 8.46.24\u202FAM.png](https://assets.leetcode.com/users/images/3f2f64b9-39f6-4e4e-b7bf-9bc6aabc2153_1698723928.257756.png)\n\n# Intuition:\n\n**If we have an array of prefix sums pref, then the original array arr can be recovered by taking the prefix sum of pref. That is, arr[i] = pref[i] ^ pref[i-1] for i > 0 and arr[0] = pref[0]. This is because pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] ^ arr[i], so pref[i] ^ pref[i-1] = arr[i].** \n\n# Algorithm:\n1. Initialize ans = [0] * n, where n is the length of pref.\n2. ans[0] = pref[0] because pref[0] = arr[0] ^ arr[1] ^ ... ^ arr[n-1] = arr[0].\n3. For i in range(1, n), ans[i] = pref[i] ^ pref[i-1]. This is because pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] ^ arr[i], so pref[i] ^ pref[i-1] = arr[i].\n4. Return ans.\n\n# Complexity Analysis:\n- Time Complexity: **O(n)**, where n is the length of pref.\n- Space Complexity: **O(n)**, the space used by ans.\n\n# Code\n``` Python []\nclass Solution:\n    def findArray(self, pref: List[int]) -> List[int]:\n        n = len(pref)\n        ans = [0] * n\n        ans[0]=pref[0]\n        for i in range(1,n):\n            ans[i]=pref[i]^pref[i-1]\n        return ans\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<int> findArray(vector<int>& pref) {\n        int n = pref.size();\n        vector<int> ans(n, 0);\n        ans[0] = pref[0];\n        for (int i = 1; i < n; i++) {\n            ans[i] = pref[i] ^ pref[i - 1];\n        }\n        return ans;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int[] findArray(int[] pref) {\n        int n = pref.length;\n        int[] ans = new int[n];\n        ans[0] = pref[0];\n        for (int i = 1; i < n; i++) {\n            ans[i] = pref[i] ^ pref[i - 1];\n        }\n        return ans;\n    }\n}\n```\n# Approach 2: Prefix Sum (In-Place)\n![Screenshot 2023-10-31 at 8.41.36\u202FAM.png](https://assets.leetcode.com/users/images/da9f3c8a-7436-4237-aa8e-b8bd64ae8f76_1698723152.8690343.png)\n\n# Intuition:\n**If we have an array of prefix sums pref, then the original array arr can be recovered by taking the prefix sum of pref. That is, arr[i] = pref[i] ^ pref[i-1] for i > 0 and arr[0] = pref[0]. This is because pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] ^ arr[i], so pref[i] ^ pref[i-1] = arr[i].**\n\n# Algorithm:\n1. For i in range(1, n), pref[i] ^= pref[i-1]. This is because pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] ^ arr[i], so pref[i] ^ pref[i-1] = arr[i].\n2. Return pref.\n\n# Complexity Analysis:\n- Time Complexity: **O(n)**, where n is the length of pref.\n- Space Complexity: **O(1)**, the space used by pref.\n\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``` 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``` Java []\nclass 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\n# Approach 3: Reverse Prefix Sum (In-Place)\n\n![Screenshot 2023-10-31 at 8.50.27\u202FAM.png](https://assets.leetcode.com/users/images/4e7d5e44-f062-477a-ba61-52431e25b21c_1698723951.138558.png)\n\n# Intuition:\n**If we to find out the prefix sum of pref, we will be doing it in by pref[i]=pref[i]^pref[i-1]. But when we do it in reverse order. We don\'t \nhave to create a new array. We can just do it in place.**\n\n# Algorithm:\n1. For i in range(n-1, 0, -1), pref[i] ^= pref[i-1]. This is because pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] ^ arr[i], so pref[i] ^ pref[i-1] = arr[i].\n2. Return pref.\n\n# Complexity Analysis:\n- Time Complexity: **O(n)**, where n is the length of pref.\n- Space Complexity: **O(1)**, the space used by pref.\n# Code\n``` Python []\nclass Solution:\n    def findArray(self, pref):\n        for i in range(len(pref) - 1, 0, -1):\n            pref[i] = (pref[i] ^ pref[i-1])\n        return pref\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<int> findArray(vector<int>& pref) {\n        for (int i = pref.size() - 1; i > 0; i--) {\n            pref[i] = (pref[i] ^ pref[i-1]);\n        }\n        return pref;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int[] findArray(int[] pref) {\n        for (int i = pref.length - 1; i > 0; i--) {\n            pref[i] = (pref[i] ^ pref[i-1]);\n        }\n        return pref;\n    }\n}\n```
['Array', 'Math', 'Bit Manipulation', 'Prefix Sum', 'C++', 'Java', 'Python3']