Python || O(log(n)) time, O(1) space || Faster than 100% || Explained and compared
Approach\nFor all the solutions presented here, the general approach is as follows:\n- Step #1: Identify the digits n is made of.\n- Step #2: Identify the power
# Approach\nFor all the solutions presented here, the general approach is as follows:\n- **Step #1**: Identify the digits `n` is made of.\n- **Step #2**: Identify the powers of 2 that have the same number of digits as `n`; there are maximum four of them.\n- **Step #3**: Check whether any of the powers of 2 from step **#2** are made of the same digits as identified in step **#1**.\n\n# Solution with the lowest time and space theoretical complexity\n**Description**\nThis solution uses:\n- Integer division by 10 and modulo base 10 to identify the digits making up a given integer value.\n- A `dict` to count the number of occurrences of each digit in a given integer value.\n  Such a dict has maximum 10 entries.\n- The comparison between such `dict` instances to check whether two integer values are made up the same digits.\n\n**Complexity**\n- Time: `O(log(n))`\n- Space: `O(1)`\n\n**Code**\nThe code below gave me: `Runtime: 26 ms, faster than 100.00% of Python3 online submissions`\n```\nfrom collections import defaultdict\n\nclass Solution:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        # Step #1: Get the digits of `n` and count their occurrences\n        # - Time: O(log(n))\n        # - Space: O(1), as `digitCounts` has maximum 10 entries\n        tmpValue, numDigits, digitCounts = n, 0, defaultdict(int)\n        while tmpValue != 0:\n            numDigits += 1\n            tmpValue, digit = divmod(tmpValue, 10)\n            digitCounts[digit] += 1\n\n        # Step #2: Identify the smallest power of 2 that has the same number of digits as `n`\n        # - Time: O(log(n))\n        # - Space: O(1)\n        minTargetValue = 10 ** (numDigits - 1)\n        powerOf2 = 1 << ceil(log2(minTargetValue))\n\n        # Step #3: Out of the powers of 2 that have the same number of digits as `n` (there are maximum four), check if any has the same digits as `n`\n        # For this, we count digit occurrences and compare to the ones from step #1\n        # - Time: O(log(n))\n        # - Space: O(1), as `powerOf2DigitCounts` has maximum 10 entries\n        maxTargetValue = 10 * minTargetValue - 1\n        while powerOf2 <= maxTargetValue:\n            tmpValue, powerOf2DigitCounts = powerOf2, defaultdict(int)\n            while tmpValue != 0:\n                numDigits += 1\n                tmpValue, digit = divmod(tmpValue, 10)\n                powerOf2DigitCounts[digit] += 1\n            if powerOf2DigitCounts == digitCounts:\n                return True\n            powerOf2 <<= 1\n\n        return False\n```\n\n# Faster solution: Use string conversion to get the digits\n**Description**\nThis solution uses:\n- String conversion to identify the digits making up a given integer value.\n- A `dict` to count the number of occurrences of each digit in a given integer value.\n  Such a dict has maximum 10 entries.\n- The comparison between such `dict` instances to check whether two integer values are made up the same digits.\n\n**Complexity**\n- Time: `O(log(n))`\n- Space: `O(log(n))`\n\n**Code**\nThe code below gave me: `Runtime: 28 ms, faster than 100.00% of Python3 online submissions`\nAgainst LeetCode\'s test suite, this timing does not look as good as the previous solution, **BUT** this is due to LeetCode\'s:\n- Huge variance in running times, even for the exact same code.\n- Test suites often no being comprehensive enough to properly differentiate algorithms.\n\nPlease see the *comparison* section at the end of this post to get a clear picture that this solution is globally faster than the previous one.\n\n```\nfrom collections import defaultdict\n\nclass Solution:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        # Step #1: Get the digits of `n` and count their occurrences\n        # - Time: O(log(n))\n        # - Space: O(log(n)) for the intermediate string\n        nStr = str(n)\n        numDigits = len(nStr)\n        digitCounts = defaultdict(int)\n        for digit in nStr:\n            digitCounts[digit] += 1\n\n        # Step #2: Identify the smallest power of 2 that has the same number of digits as `n`\n        # - Time: O(log(n))\n        # - Space: O(1)\n        minTargetValue = 10 ** (numDigits - 1)\n        powerOf2 = 1 << ceil(log2(minTargetValue))\n\n        # Step #3: Out of the powers of 2 that have the same number of digits as `n` (there are maximum four), check if any has the same digits as `n`\n        # For this, we count digit occurrences and compare to the ones from step #1\n        # - Time: O(log(n))\n        # - Space: O(log(n)) for the intermediate strings\n        maxTargetValue = 10 * minTargetValue - 1\n        while powerOf2 <= maxTargetValue:\n            powerOf2Str = str(powerOf2)\n            powerOf2DigitCounts = defaultdict(int)\n            for digit in powerOf2Str:\n                powerOf2DigitCounts[digit] += 1\n            if powerOf2DigitCounts == digitCounts:\n                return True\n            powerOf2 <<= 1\n\n        return False\n```\n\n# Fastest solution: Sort the digits rather than counting their occurrences\n**Description**\nThis solution uses:\n- String conversion to identify the digits making up a given integer value.\n- Sorting of the digits.\n- The comparison between such sorted lists to check whether two integer values are made up the same digits.\n\n**Complexity**\n- Time: `O(log(n)*log(log(n)))`\n- Space: `O(log(n))`\n\nAlthough the theoretical time complexity is worse than the previous solutions, in practice this performs noticeable faster, as:\n- We are talking about a relatively small number of digits, so the sorting is actually very fast.\n- The building of a list structure is much faster than the building of a counter dictionary structure.\n\n**Code**\nThe code below gave me: `Runtime: 23 ms, faster than 100.00% of Python3 online submissions`\nPlease see the *comparison* section at the end of this post to get a better sense of how much faster this solution actually is.\n```\nclass Solution:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        # Step #1: Get the digits of `n` and sort them\n        # - Time: O(log(n)*log(log(n)))\n        # - Space: O(log(n))\n        nStr = str(n)\n        numDigits, sortedDigits = len(nStr), sorted(nStr)\n\n        # Step #2: Identify the smallest power of 2 that has the same number of digits as `n`\n        # - Time: O(log(n))\n        # - Space: O(1)\n        minTargetValue = 10 ** (numDigits - 1)\n        powerOf2 = 1 << ceil(log2(minTargetValue))\n\n        # Step #3: Out of the powers of 2 that have the same number of digits as `n` (there are maximum four), check if any has the same digits as `n`\n        # For this, we sort the digits and compare to the ones from step #1\n        # - Time: O(log(n)*log(log(n)))\n        # - Space: O(log(n))\n        maxTargetValue = 10 * minTargetValue - 1\n        while powerOf2 <= maxTargetValue:\n            powerOf2Str = str(powerOf2)\n            if sorted(powerOf2Str) == sortedDigits:\n                return True\n            powerOf2 <<= 1\n\n        return False\n```\n\n# Timings comparison\nAs mentioned previously, one cannot rely on LeetCode\'s test suites or LeetCode\'s inconsistent running times to get a proper picture of how different algorithms actually compare.\n\nSo, here is some code that compares the 3 solutions presented above, and that anyone can run on their own machine.\nIt generates 1,000,000 test cases with integers of varying sizes; out of these, 332 can be reordered into a power of 2.\n\n**Code**\n```\n# ==================================================================================================\n# Solution with the lowest time and space theoretical complexity\n# ==================================================================================================\n\nfrom collections import defaultdict\nfrom math import ceil, log2\n\nclass Solution_1:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        tmpValue, numDigits, digitCounts = n, 0, defaultdict(int)\n        while tmpValue != 0:\n            numDigits += 1\n            tmpValue, digit = divmod(tmpValue, 10)\n            digitCounts[digit] += 1\n\n        minTargetValue = 10 ** (numDigits - 1)\n        powerOf2 = 1 << ceil(log2(minTargetValue))\n\n        maxTargetValue = 10 * minTargetValue - 1\n        while powerOf2 <= maxTargetValue:\n            tmpValue, powerOf2DigitCounts = powerOf2, defaultdict(int)\n            while tmpValue != 0:\n                numDigits += 1\n                tmpValue, digit = divmod(tmpValue, 10)\n                powerOf2DigitCounts[digit] += 1\n            if powerOf2DigitCounts == digitCounts:\n                return True\n            powerOf2 <<= 1\n\n        return False\n\n# ==================================================================================================\n# Faster solution: Use string conversion to get the digits\n# ==================================================================================================\n\nfrom collections import defaultdict\nfrom math import ceil, log2\n\nclass Solution_2:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        nStr = str(n)\n        numDigits = len(nStr)\n        digitCounts = defaultdict(int)\n        for digit in nStr:\n            digitCounts[digit] += 1\n\n        minTargetValue = 10 ** (numDigits - 1)\n        powerOf2 = 1 << ceil(log2(minTargetValue))\n\n        maxTargetValue = 10 * minTargetValue - 1\n        while powerOf2 <= maxTargetValue:\n            powerOf2Str = str(powerOf2)\n            powerOf2DigitCounts = defaultdict(int)\n            for digit in powerOf2Str:\n                powerOf2DigitCounts[digit] += 1\n            if powerOf2DigitCounts == digitCounts:\n                return True\n            powerOf2 <<= 1\n\n        return False\n\n# ==================================================================================================\n# Fastest solution: Sort the digits rather than counting their occurrences\n# ==================================================================================================\n\nfrom math import ceil, log2\n\nclass Solution_3:\n    def reorderedPowerOf2(self, n: int) -> bool:\n        nStr = str(n)\n        numDigits, sortedDigits = len(nStr), sorted(nStr)\n\n        minTargetValue = 10 ** (numDigits - 1)\n        powerOf2 = 1 << ceil(log2(minTargetValue))\n\n        maxTargetValue = 10 * minTargetValue - 1\n        while powerOf2 <= maxTargetValue:\n            powerOf2Str = str(powerOf2)\n            if sorted(powerOf2Str) == sortedDigits:\n                return True\n            powerOf2 <<= 1\n\n        return False\n\n# ==================================================================================================\n# Testing\n# ==================================================================================================\n\nfrom time import perf_counter\n\npowersOf2sortedDigits = frozenset(tuple(sorted(str(powerOf2))) for powerOf2 in (2 ** i for i in range(31)))\ntestCases = [(n, tuple(sorted(str(n))) in powersOf2sortedDigits) for n in (137 * i for i in range(1, 1000001))]\nprint(f"{len(testCases)} test cases out of which {sum(1 for _, expected in testCases if expected is True)} return `True`")\n\nfor Solution in [Solution_1, Solution_2, Solution_3]:\n    print(f"*** {Solution.__name__} ***")\n    startPerfCounter = perf_counter()\n    for n, expected in testCases:\n        actual = Solution().reorderedPowerOf2(n)\n        assert actual == expected, f"ERROR for arg {n}:\\n- Expected: {expected}\\n- Got: {actual}"\n    else:\n        endPerfCounter = perf_counter()\n        print(f"Completed in {(endPerfCounter - startPerfCounter)}s")\n```\n\n**Results**\nRunning this code on my laptop, I got:\n```\n1000000 test cases out of which 332 return `True`\n*** Solution_1 ***\nCompleted in 10.228865999999925s\n*** Solution_2 ***\nCompleted in 7.209750700000313s\n*** Solution_3 ***\nCompleted in 3.2113036999999167s\n```
['Python', 'Python3']