【Video】Give me 5 minutes - How we think about a solution - Python, JavaScript, Java, C++
Intuition\nThis is similar to prefix sum\n\n---\n\n# Solution Video\n\nhttps://youtu.be/ck4dJURKAlA\n\n\u25A0 Timeline of the video\n0:05 Solution code with bui
# Intuition\nThis is similar to prefix sum\n\n---\n\n# Solution Video\n\nhttps://youtu.be/ck4dJURKAlA\n\n\u25A0 Timeline of the video\n`0:05` Solution code with build-in function\n`0:06` quick recap of XOR calculation\n`0:28` Demonstrate how to solve the question\n`1:37` How you keep the original previous number\n`2:29` Continue to demonstrate how to solve the question\n`3:59` Coding\n`4:43` Time Complexity and Space Complexity\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,898\nMy initial goal is 10,000\nThank you for your support!\n\n---\n\n# Approach\n\n## How we think about a solution\n\nTo be honest, there is no complicated logic this time. This is similar to prefix sum, so we can calculate `XOR` with the input numbers one by one.\n\n```\nInput: pref = [5,2,0,3,1]\n```\n\n##### Quick recap of XOR caluclation\n---\nIf one of numbers is 1 and the other is 0 \u2192 1\nIf both numbers are 1 \u2192 0\nIf both numbers are 0 \u2192 0\n\n---\n\n\n\nFirst of all, we calculate `5`, but there is no previous number, so it is considered as `0`\n\n```\n101 (= 5)\n000 (= 0)\n---\n101 (= 5)\n\n```\nActually, we can start from `index 1` in real solution code, becuase the number at index 0 never change.\n\nMy solution starts from here. In the solution code, I update input array `pref` itself.\n```\nindex = 1\n\n010 (= 2)\n101 (= 5)\n---\n111 (= 7)\n\npref = [5, 7, 0, 3, 1]\n```\nBut problem is we need `2` for the next calculation, because `2` is the previous original number of intput array. How do you get `2`.\n\nIt\'s simple.\n```\n2 ^ 5 = 7 \n```\nThis is similar to \n```\n80 + 20 = 100\n\u2193\n80 = 100 - 20\n```\n```\n2 ^ 5 = 7 \n\u2193\n2 = 7 ^ 5\n\n111 (= 7)\n101 (= 5)\n---\n010 (= 2)\n\n```\n---\n\n\u2B50\uFE0F Points\n\nCalculate a previous number we need for the next calculation before we move the next iteration.\n```\n(next)prev = pref[i] ^ (current)prev\n\npref[i] is a current result\n```\n---\n\nWe use `prev` for the next calculation.\n```\nprev = 2\npref = [5, 7, 0, 3, 1]\n```\n```\nindex = 2\n\n000 (= 0 from input array)\n010 (= 2 from prev)\n---\n010 (= 2)\n\npref = [5, 7, 2, 3, 1]\nprev = 0 (= 2 ^ 2) \n```\n```\nindex = 3\n\n011 (= 3 from input array)\n000 (= 0 from prev)\n---\n011 (= 3)\n\npref = [5, 7, 2, 3, 1]\nprev = 3 (= 0 ^ 3) \n```\n\n```\nindex = 4\n\n001 (= 1 from input array)\n011 (= 3 from prev)\n---\n010 (= 2)\n\npref = [5, 7, 2, 3, 2]\nprev = 1 (= 3 ^ 2) \n```\n```\npref: [5,7,2,3,2] (Output)\n```\n\n---\n\n\n\n### Algorithm Overview:\nThe algorithm takes an input list `pref` of integers and transforms it in-place.\n\n### Detailed Explanation:\n1. Initialize a variable `prev` with the value of the first element in the `pref` list.\n2. Start a loop from the second element (index 1) to the last element of the `pref` list.\n3. Inside the loop, perform a bitwise XOR operation (`^`) between the current element at index `i` and the `prev` value. This replaces the current element with the XOR result.\n4. Update the `prev` value by performing a bitwise XOR operation between the previous `prev` value and the updated current element.\n5. Repeat steps 3-4 for all elements in the `pref` list.\n6. Return the modified `pref` list. The input list has been transformed in-place, with each element being XORed with the cumulative XOR of all previous elements.\n\n\n---\n\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\nIf we can update input array. My solution code updates it directly. But if we can\'t, space complexity should be $$O(n)$$ for result array. You need to ask interviewers about it in real interviews.\n\n\n```python []\nclass Solution:\n    def findArray(self, pref: List[int]) -> List[int]:\n        \n        prev = pref[0]\n\n        for i in range(1, len(pref)):\n            pref[i] ^= prev\n            prev ^= pref[i]\n        \n        return pref\n```\n```javascript []\n/**\n * @param {number[]} pref\n * @return {number[]}\n */\nvar findArray = function(pref) {\n    let prev = pref[0];\n    \n    for (let i = 1; i < pref.length; i++) {\n        pref[i] ^= prev;\n        prev ^= pref[i];\n    }\n    \n    return pref;    \n};\n```\n```java []\nclass Solution {\n    public int[] findArray(int[] pref) {\n        int prev = pref[0];\n        \n        for (int i = 1; i < pref.length; i++) {\n            pref[i] ^= prev;\n            prev ^= pref[i];\n        }\n        \n        return pref;        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> findArray(vector<int>& pref) {\n        int prev = pref[0];\n        \n        for (int i = 1; i < pref.size(); i++) {\n            pref[i] ^= prev;\n            prev ^= pref[i];\n        }\n        \n        return pref;        \n    }\n};\n```\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u25A0 Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/find-mode-in-binary-search-tree/solutions/4233557/video-give-me-5-minutes-how-we-think-about-a-solution-why-do-we-use-inorder-traversal/\n\nvideo\nhttps://youtu.be/0i1Ze62pTuU\n\n\u25A0 Timeline of the video\n`0:04` Which traversal do you use for this question?\n`0:34` Properties of a Binary Search Tree\n`1:31` Key point of my solution code\n`3:09` How to write Inorder, Preorder, Postorder\n`4:08` Coding\n`7:13` Time Complexity and Space Complexity\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,908\nMy initial goal is 10,000\nThank you for your support!\n\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/solutions/4225041/video-give-me-10-minutes-using-heap-without-build-in-function-such-as-sort-or-bit-count/\n\nvideo\nhttps://youtu.be/oqV8Ai0_UWA\n\n\u25A0 Timeline\n`0:05` Solution code with build-in function\n`0:26` Two difficulties to solve the question\n`0:41` How do you count 1 bits?\n`1:05` Understanding to count 1 bits with an example\n`3:02` How do you keep numbers in ascending order when multiple numbers have the same number of 1 bits?\n`5:29` Coding\n`7:54` Time Complexity and Space Complexity
['C++', 'Java', 'Python3', 'JavaScript']