✅ From brute force to optimziation | Fully Explained
In this post, I shared my full thought process behind the question, and how I arrived at the optimal solution.\n\nIn contrast to just posting the answer, I try 
In this post, I shared my full thought process behind the question, and how I arrived at the optimal solution.\n\nIn contrast to just posting the answer, I try to teach and show how to tackle problems and arrive progressively at the optimal solution, instead of memorizing them :)\n\n<hr />\n\nThe problem states that we are given an integer `n` and we can rearrange it in any order, except leading zero. And we need to check whether we can arrive at a valid power of 2.\n\nIn such questions, it\'s very important to look at the **constraints** because a lot of times it can contradict/hint toward specific solutions. In our case `1 <= n <= 10^9`\n\nGiven the constraints, we know that we can have at most 10 digits in n. So generating all permutations will cost us n!, which is **10!** => **3,628,800** (A little less because 0 is invalid in the first position. But that\'s an upper bound)\n\nAlso, we know that a 32-bit integer has 31 powers of 2. You can just shift the active bit to the left. (1 bit it taken for the sign)\n\nSo the initial idea can be to generate a set containing all the powers of 2, and to generate a set of all the permutations, and then check whether there is an element that is intersecting between both sets.\n\n# Naive brute force\n\n```\nclass Solution:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        int32_powers_of_two = set()\n        for i in range(31):\n            int32_powers_of_two.add(1<<i)\n        \n        n_numbers = []\n        while n > 0:\n            n_numbers.append(n % 10)\n            n //= 10\n        \n        permutations = set()\n        def generate_permutations(cur_permutation, options):\n            if not options:\n                permutations.add(int(cur_permutation))\n                return\n            \n            for i in range(len(options)):\n                if cur_permutation == "" and options[i] == 0: continue\n                generate_permutations(cur_permutation + str(options[i]), [*options[:i], *options[i+1:]])\n        \n        generate_permutations("", n_numbers)\n        return permutations.intersection(int32_powers_of_two)\n```\n\nThat will TLE on the last test cases. Let\'s optimize\n\n# Optimization\n\nOne observation that we can make is that we don\'t need to generate all the permutations for n. \n\nLet\'s say `n` is `4210`\n\nIt\'s enough for us to look at the powers of two that have 4 digits. i.e. [1024, 2048, 4096, 8192]\n\nTake a look, can `n` be reordered to a power of 2? how would you know that efficiently?\n\nWhenever you are asked about ordering/shuffling and equality, think about sorting. Sorting will represent the lexicographical order, and if both lexicographical orders are equal, you can reshuffle A to get B.\n\nIf we sort `n` = `4210` -> `0124`\nIf we sort `1024` (a power of 2) -> `0124`\n\nBoth are equal, hence we can reorder n to get a power of two.\n\n# Algorithm\n1. We will generate all permutations of 2 within the 32-bit integer range, but store them in buckets relevant to their digit count. This will allow us to look at the powers of 2 that have the same digit count as n\n2. We will sort `n` (transform to string and sort) and compare against all powers of 2 with the same digit count sorted.\n3. If we find the same lexicographical order, we can reorder to a valid power of 2. \n4. If non-matched, we return false after the iteration.\n\n\n```\nclass Solution:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        buckets = [[] for _ in range(11)]\n        for i in range(31):\n            power_of_two = 1<<i\n            digits_count = math.floor(math.log10(power_of_two)) + 1\n            buckets[digits_count].append(power_of_two)\n        \n        n_str_sorted = "".join(sorted(str(n)))\n        n_digits_count = math.floor(math.log10(n)) + 1\n        for power_of_two in buckets[n_digits_count]:\n            if n_str_sorted == "".join(sorted(str(power_of_two))):\n                return True\n        return False\n```\n\n# Further notes\n* Instead of sorting you could also count the character frequency and check whether any power of 2 has the same count character count as `n`\n* Feel free to add a comment with the code in a different language so I\'ll add them to the post and mention your name.\n\n<hr />\nHave a great day!\n\nIf you found this read helpful, please upvote.\nIt motivates me to do more of them, and also shows me that these posts are helpful for some folks.\n
['Python']