[Python3] Brute-Force -> Greedy - Detailed Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- Using pen and draw some examples and recognized the pattern\n\n\nInput | Answer | Inp
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Using pen and draw some examples and recognized the pattern\n\n```\nInput | Answer | Input | Answer\n-------------------------------\n2           -1      10\n3            1      11       1\n5            4     101     100\n7            3     111      11\n11           9    1011    1001\n13          12    1101    1100\n17          16   10001   10000\n19          17   10011   10001\n31          15   11111    1111\n```\n\n- From the expamples I drawn It is recognized that the `answer` is the original number removing the most-left `1` bit of the continous 1 chain from starting from the right.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**`helper(num)` function:**\n\n**1. Base Case:**\n\n- `if num == 2: return -1`\n    - This handles a specific case where the input number is 2. It directly returns -1 for this case. It seems like a special condition for this particular problem.\n\n**2. Binary Conversion:**\n\n- `bin_arr = [0] + list(map(int, bin(num)[2:]))`\n    - `bin(num)` converts the integer num to its binary representation as a string (e.g., `bin(5)` returns `"0b101"`).\n- `[2:]` slices the string to remove the "0b" prefix.\n- `map(int, ...)` converts each character (\'1\' or \'0\') in the string to an integer.\n- `list(...)` creates a list of these integers.\n- `[0] + ...` adds a leading 0 to the list. This is likely done to handle potential edge cases during the bit manipulation later.\n\n**3. Bit Manipulation:**\n\n- `for i in range(len(bin_arr) - 1, -1, -1):`\n    - This loop iterates through the `bin_arr` in reverse order (from the least significant bit to the most significant bit).\n    - `if bin_arr[i] == 0:`\n        - If a 0 bit is found:\n            - `bin_arr[i + 1] = 0` : The next higher bit (to the left) is set to 0.\n            - `break`: The loop terminates after this change.\n    - This part seems to be designed to modify the binary representation in a specific way. It essentially finds the rightmost \'1\' bit and sets the bit to its left to \'0\'.\n    \n**4. Decimal Conversion:**\n\n- `res = power = 0`\n    - Initializes `res` (to store the result) and `power` (to keep track of the power of 2) to 0.\n- `for i in range(len(bin_arr) - 1, -1, -1):`\n    - This loop iterates through the modified `bin_arr` in reverse order.\n    - `res += bin_arr[i] * (2 ** power)`\n        - This calculates the decimal value of each bit and adds it to `res`.\n    - `res + bin_arr[i]`\n    - `power += 1`\n        - Increments the `power` for the next bit.\n- `return res`: Returns the calculated decimal value.\n\n**`minBitwiseArray(nums)` function:**\n\n- `return [helper(num) for num in nums]`\n    - This uses list comprehension to apply the `helper` function to each number in the input list `nums` and returns a new list with the transformed values.\n\n**Overall, the code seems to be designed to:**\n\n1. Convert each number in the input list to its binary representation.\n2. Modify the binary representation by finding the rightmost \'1\' and setting the bit to its left to \'0\'.\n3. Convert the modified binary representation back to decimal.\n\n# Code\n##### 1. Brute-Force\n```python3 []\nclass Solution:\n    def minBitwiseArray(self, nums: List[int]) -> List[int]:\n        def helper(num: int) -> int:\n            for new_num in range(num):\n                if new_num | (new_num + 1) == num: return new_num\n            return -1\n        \n        return [helper(num) for num in nums]\n```\n\n- Time complexity: $$O(N * M)$$ with `N` is the number of number in `nums` and `M` is the number in `nums`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n##### 2. Greedy\n```\nclass Solution:\n    def minBitwiseArray(self, nums: List[int]) -> List[int]:\n        def helper(num: int) -> int:\n            if num == 2: return -1\n            bin_arr = [0] + list(map(int, bin(num)[2:]))\n            for i in range(len(bin_arr) - 1, -1, -1):\n                if bin_arr[i] == 0:\n                    bin_arr[i + 1] = 0\n                    break\n            res = power = 0\n            for i in range(len(bin_arr) - 1, -1, -1):\n                res += bin_arr[i] * (2 ** power)\n                res + bin_arr[i]\n                power += 1\n            return res\n        \n        return [helper(num) for num in nums]\n```\n- Time complexity: $$O(N * 32)$$ with `N` is the number of number in `nums` and `M` is the number in `nums`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Greedy', 'Bit Manipulation', 'Python3']