Binary Search - Python 3 - Beats 100% for now
Intuition\nfind the minimum cost of this below graphic. You can see we want to find the reversal point.\n\nYou can see this below for the intuition\n\n\n\n# App
# Intuition\nfind the minimum cost of this below graphic. You can see we want to find the reversal point.\n\nYou can see this below for the intuition\n![image.png](https://assets.leetcode.com/users/images/78ff2468-f435-4f08-9001-407c88be247b_1702798046.124087.png)\n\n\n# Approach 1\nThe first approach is to brute force palindrome numbers from \n1 to 999999999 and check for the reversal point. \nThe complexity would too much\n\n# Approach 2\n1. We will generate palindrome numbers from 1-999999999, the total palindrome numbers generated is 10^5(the exact numbers of palindrome generated is 109999)\n2. Sort the palindromes number generated\n3. we will use binary search to prune (you can see my code as how to prune the result)\n# Complexity\n- Time complexity Approach 2:\n1. Generating palindromes would be 10^5\n2. sorting would be (10^5)log(10^5)\n3. binary search would be nlog(10^5)\ntotal would be = nlog(10^5) + (10^5)log(10^5) + 10^5\nwe can simplify to = nlog(10^5)\n- Space complexity Approach 2:\nspace complexity = 10^5\n\n# Code\n```\ndef generatePalindrome(result, temp):\n    if len(temp)==4:\n        res = str(int("".join(temp)))\n        res = "" if res=="0" else res\n        if res!="":\n            result.append(int(res+res[::-1]))\n        for i in range(10):\n            result.append(int(res + str(i) + res[::-1]))\n        return result\n    for i in range(10):\n        temp.append(str(i))\n        generatePalindrome(result, temp)\n        temp.pop()\n    return result\n        \npalindromes = generatePalindrome([],[])\npalindromes.sort()\n\n\nclass Solution:\n    def minimumCost(self, nums: List[int]) -> int:\n        \n        def calcCost(target):\n            cost = 0\n            for num in nums:\n                cost+= abs(target-num)\n            return cost\n\n        left = 0\n        right = len(palindromes)-2\n        \n        while left<right:\n            mid = left + (right-left)//2\n            midCost = calcCost(palindromes[mid])\n            nextMidCost = calcCost(palindromes[mid+1])\n            if midCost<=nextMidCost:\n                right = mid\n            else:\n                left = mid+1\n        if left==len(palindromes)-2:\n            return min(calcCost(palindromes[left]), calcCost(palindromes[left+1]))\n        else:\n            return calcCost(palindromes[left])  \n```\n\n\nlet me know if you have any suggestions.\n![image.png](https://assets.leetcode.com/users/images/f71343c4-b59f-437f-9e08-3ee5d79812b9_1702798715.3004112.png)\n
['Binary Search', 'Sorting', 'Python3']