Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Reordering changes digit positions but not digit frequencies. Instead of generating permutations, compare the input's digit multiset with each possible power of two. A matching power itself supplies a valid ordering without a leading zero.

Approach

Count every decimal digit in n, including zeros.
Generate powers of two beginning at one while the value is at most one billion. Build a digit-frequency map for each.
Return true when the maps match exactly; matching just the set of digits would lose repeated-digit counts. Otherwise return false after the candidates are exhausted.
This candidate limit is sufficient: inputs below one billion have at most nine digits, while the only allowed ten-digit input, one billion itself, cannot rearrange into a power of two.

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        map = defaultdict(int)
        s = str(n)

        for x in s:
            map[x] += 1

        curr = 1

        while curr <= 10**9:
            map2 = defaultdict(int)
            s2 = str(curr)
            for x in s2:
                map2[x] += 1
            if map == map2:
                return True
            curr *= 2

        return False
        # O(digits)

Complexity analysis

Let d be the maximum digit count and P the number of powers of two checked (at most 30 here). Both displayed implementations build and compare digit-frequency maps in O(Pd) time and O(d) auxiliary space; these bounds are effectively constant under the fixed numeric limit.