Problem of The Day: Reordered Power of 2

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        str_num = str(n)
        arr = list(str_num)

        def isPowerOfTwo(curr_string):
            num = int(curr_string)
            return num > 0 and (num & (num - 1)) == 0

        def helper(start, curr):
            if start > len(curr):
                return False
            for i in range(start, len(curr)):
                curr[i], curr[start] = curr[start], curr[i]
                if curr[0] == '0':
                    continue
                curr_num = ''.join(curr)
                if isPowerOfTwo(curr_num):
                    return True
                ans = helper(start + 1, curr)
                if ans:
                    return True
                curr[i], curr[start] = curr[start], curr[i]
            return False
        return helper(0, arr)

• Time: O(N!)
• Space: O(N!)

Editorial

Approach 1: Permutations

class Solution(object):
    def reorderedPowerOf2(self, N):
        """
        Let's work through an example like N = 128.
        In the last line, 'for cand in itertools.permutations(str(N))' will
        iterate through the six possibilities cand = ('1', '2', '8'),
        cand = ('1', '8', '2'), cand = ('2', '1', '8'), and so on.

        The check cand[0] != '0' is a check that the candidate permutation
        does not have a leading zero.

        The check bin(int("".join(cand))).count('1') == 1 is a check that cand
        represents a power of 2: namely, that the number of ones in its binary
        representation is 1.
        """
        return any(cand[0] != '0' and bin(int("".join(cand))).count('1') == 1
                   for cand in itertools.permutations(str(N)))

Approach 2: Counting

class Solution(object):
    def reorderedPowerOf2(self, N):
        count = collections.Counter(str(N))
        return any(count == collections.Counter(str(1 << b))
                   for b in xrange(31))