# Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the
#  leading digit is not zero.
#
# Return true if and only if we can do this in a way such that the resulting number is a power of 2.
#
#
#
# Example 1:
#
# Input: 1
# Output: true
# Example 2:
#
# Input: 10
# Output: false
# Example 3:
#
# Input: 16
# Output: true
# Example 4:
#
# Input: 24
# Output: false
# Example 5:
#
# Input: 46
# Output: true
#
#
# Note:
#
# 1 <= N <= 10^9
import collections
import math


class Solution(object):
    def reorderedPowerOf2(self, N):
        """
        :type N: int
        :rtype: bool
        """

        L = sorted(str(N))
        N1 = "".join(L)
        if N1[0] == 0:
            N1 = N1[1:2] + '0' + N1[2:]
        N1 = int(N1)
        N2 = int("".join(L)[::-1])

        t1, t2 = math.floor(math.log(N1, 2)), math.ceil(math.log(N2, 2))

        for i in xrange(int(t1), int(t2) + 1):
            if collections.Counter(str(1 << i)) == collections.Counter(str(N)):
                return True

        return False

    def reorderedPowerOf2_1(self, N):
        """
        :type N: int
        :rtype: bool
        """
        count = collections.Counter(str(N))

        return any(count == collections.Counter(str(1 << b)) for b in xrange(31))


if __name__ == '__main__':
    print Solution().reorderedPowerOf2(1)
    print Solution().reorderedPowerOf2(2)
    print Solution().reorderedPowerOf2(3)
    print Solution().reorderedPowerOf2(61)
    print Solution().reorderedPowerOf2(23)
    print Solution().reorderedPowerOf2(4021)
