Solution


Approach 1: Permutations

Intuition

For each permutation of the digits of N, let's check if that permutation is a power of 2.

Algorithm

This approach has two steps: how will we generate the permutations of the digits, and how will we check that the permutation represents a power of 2?

To generate permutations of the digits, we place any digit into the first position (start = 0), then any of the remaining digits into the second position (start = 1), and so on. In Python, we can use the builtin function itertools.permutations.

To check whether a permutation represents a power of 2, we check that there is no leading zero, and divide out all factors of 2. If the result is 1 (that is, it contained no other factors besides 2), then it was a power of 2. In Python, we can use the check bin(N).count('1') == 1.

Complexity Analysis

  • Time Complexity: . Note that is the number of digits in the binary representation of . For each of permutations of the digits of , we need to check that it is a power of 2 in time.

  • Space Complexity: , the space used by A (or cand in Python).


Approach 2: Counting

Intuition and Algorithm

We can check whether two numbers have the same digits by comparing the count of their digits. For example, 338 and 833 have the same digits because they both have exactly two 3's and one 8.

Since could only be a power of 2 with 9 digits or less (namely, ), we can just check whether has the same digits as any of these possibilities.

Complexity Analysis

  • Time Complexity: . There are different candidate powers of 2, and each comparison has time complexity.

  • Space Complexity: .


Analysis written by: @awice.