Python 3 || Bit Operation || Reuse Input List
Intuition\nMost solutions create a new list to return the result. This solution is based on reusing the input list by using bitwise operations.\n\n# Approach\nT
# Intuition\nMost solutions create a new list to return the result. This solution is based on reusing the input list by using bitwise operations.\n\n# Approach\nThe idea is to traverse the list and, if necessary, storing two values in one number. The maximum number is $$10^5$$, for which at most 17 bits are required. All other bits can be used to store the new values.\n\nWe split each number into its individual digits and store them one by one at the correct indices ```ptr``` in the list. To do this, we append the new number to the left of the original number ```int(num)<<17 | nums[ptr]```. If all elements of the list are already filled with a second value, the element is appended to the list. Finally, we remove the original value and set the new value by shifting ```nums[i] >>= 17```.\n\n\n```\nmax_number: 100000 (decimal) = 00000000 00000001 10000110 10100000 (binary)\nmask numbers:                  00000000 00000001 11111111 11111111 (2^17-1)\nusable numbers:                11111111 11111110 00000000 00000000\n```\n\n# Code\n```Python3\nclass Solution:\n    def separateDigits(self, nums: List[int]) -> List[int]:\n        ptr = 0\n        n = len(nums)\n        mask = 2**17-1\n        for i in range(n):\n            for num in str(nums[i]&mask):\n                if ptr<n:\n                    nums[ptr] = int(num)<<17 | nums[ptr]\n                    ptr += 1\n                else:\n                    nums.append(int(num))\n            nums[i] >>= 17\n        return nums\n```\n\n# Complexity\n- Time complexity: $$O(n)$$\n    - Outer loop\n    Each number is visited once\n    - Inner loop\n    For each number, we iterate all digits (at most 6 digits because max_number=$$10^5$$)\n    - Worst case: $$O(6*n)=O(n)$$\n\n- Space complexity: $$O(n)$$ \n    - Worst case\n    Input list contains max_number=$$10^5$$ n times. List must be increased by 5 additional entries for each element => $$O(6*n)=O(n)$$\n\n
['Python3']