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

Difficulty: interview

Starter code:

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        

Solutions:
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        
        n_len = len(str(n))
        n = Counter(str(n))
        
        p = 1
        while len(str(p)) <= n_len:
            if len(str(p)) == n_len and Counter(str(p)) == n:
                return True
            p *= 2
        
        return False

from collections import Counter
class Solution:
    def reorderedPowerOf2(self, N):
        c = Counter(str(N))
        for i in range(32):
            if Counter(str(1 << i)) == c:
                return True
        return False

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        
        # Because 10**9 ~ 2**30
        return sorted(str(N)) in [sorted(str(1 << i)) for i in range(30)]


class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        all_powers_of_two_up_to_limit_sorted = [sorted(str(1 << i)) for i in range(30)]
        return sorted(str(N)) in all_powers_of_two_up_to_limit_sorted


class Solution:
    def reorderedPowerOf2(self, N: int) -> bool: 
        if N==1:
            return True
        elif N==2:
            return True
       
        
        max_v = int(''.join((sorted(list(str(N)), reverse=True))))
        canidates = 2
        while True:
            print (canidates)            
            if len(str(canidates))==len(str(N)):
                canidates_memo = collections.Counter(str(canidates))
                N_memo = collections.Counter(str(N))
                success = True
                for k in canidates_memo:
                    if k not in N_memo or canidates_memo[k]!=N_memo[k]:
                        success=False
                        break
                if success:
                    return True
            if canidates<max_v:
                canidates *=2
            else:
                break
        return False
        


from collections import Counter
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        ls=[]
        for i in range(31):
            num=2**i
            ls.append(dict(Counter(str(num))))
        # print(ls)
        
        s=str(n)
        di=dict(Counter(s))
        # print(di)
        
        for i in ls:
            if(i==di):
                return True
        return False

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        
        main = list(map(Counter, [str(2**n) for n in range(0, 30)]))
        return any(Counter(str(N)) == mape for mape in main)
    
    
        1892

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        maxn = 10 ** 9
        twopower = 1
        twosets = set()
        while twopower <= maxn:
            twosets.add(twopower)
            twopower *= 2
        permutations = self.get_all_permutation(N)
        for p in permutations:
            if p[0] != '0' and int(p) in twosets:
                return True
        return False

    def get_all_permutation(self, num):
        perm = {''}
        for n in str(num):
            perm = {p[:i] + n + p[i:] for p in perm  for i in range(len(p) + 1)}
        return perm


class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        n_hash = {}
        n_str = str(N)
        for c in n_str:
            n_hash[c] = n_hash.get(c, 0) + 1
        
        for i in range(0, 31):
            num = pow(2, i)
            if len(str(num)) > len(str(N)):
                return False
            n_num = {}
            for c in str(num):
                n_num[c] = n_num.get(c, 0) + 1
            n_exists = True
            for k in n_hash:
                if n_num.get(k) and n_num.get(k) == n_hash.get(k):
                    pass
                else:
                    n_exists = False
                    break
            if n_exists:
                return True
        return False
                    
                    


import itertools

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        if N == 1:
            return True

        digits = self._getDigits(N)
        ones = {2, 4, 6, 8} & set(digits)
        if not ones:
            return False

        for o in ones:
            digits.remove(o)
            if self._canMakePowerOf2(digits, o):
                return True
            digits.append(o)
        return False

    def _getDigits(self, N):
        digits = []
        while N > 0:
            digits.append(N % 10)
            N //= 10
        return digits

    def _canMakePowerOf2(self, digits, ones):
        for seq in itertools.permutations(digits):
            if self._isPowerOf2(seq, ones):
                return True
        return False

    def _isPowerOf2(self, digits, ones):
        n = 0
        for i, d in enumerate(digits):
            if i == 0 and d == 0:
                return False
            n = 10 * n + d
        n = 10 * n + ones
        return n & (n - 1) == 0


from itertools import permutations

class Solution:
    def reorderedPowerOf2(self, x: int) -> bool:
        n = 1
        pows = set()
        for i in range(31):
            pows.add(n)
            n <<= 1        
        
        for p in permutations(str(x)):
            if p[0] == '0': continue
            if int(''.join(p)) in pows: return True
        
        return False

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        sn = sorted(str(N))
        for i in range(32):
            pot = (1 << i)
            spot = sorted(str(pot))
            if sn == spot:
                return True
        return False

from itertools import permutations
class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:

        Nstr = str(N)
        pset = set(''.join(p) for p in permutations(Nstr))
        
        bmk = 1
        while len(str(bmk)) < len(Nstr):
            bmk *= 2
        
        while len(str(bmk)) == len(Nstr):
            if str(bmk) in pset:
                return True
            bmk *= 2
        
        return False        

class Solution:
    def helper(self, level, chars):
        if level == len(chars):
            temp1 = ''.join(chars)
            if temp1[0] == '0':
                return 0
            if temp1 in self.been:
                return self.been[temp1]
            temp = bin(int(temp1)).count('1')
            if temp == 1:
                return 1
            return 0
            # while temp != 1:
            #     if temp % 2 == 0:
            #         temp = int(temp / 2)
            #     else:
            #         self.been[temp1] = 0
            #         return 0
            # self.been[temp1] = 1
            # return 1
        seen = set()
        for i in range(level, len(chars)):
            if chars[i] in seen:
                continue
            chars[level], chars[i] = chars[i], chars[level]
            h = self.helper(level + 1, chars)
            if h == 1:
                return 1
            chars[level], chars[i] = chars[i], chars[level]
            seen.add(chars[i])
        return 0
    
    def reorderedPowerOf2(self, N: int) -> bool:
        N = str(N)
        chars = [char for char in N]
        seen = set()
        self.been = {}
        for i in range(0, len(chars)):
            if self.helper(i, chars):
                return True
        return False

class Solution:
    def helper(self, level, chars):
        if level == len(chars):
            temp1 = ''.join(chars)
            if temp1[0] == '0':
                return 0
            if temp1 in self.been:
                return self.been[temp1]
            temp = int(temp1)
            while temp != 1:
                if temp % 2 == 0:
                    temp = int(temp / 2)
                else:
                    self.been[temp1] = 0
                    return 0
            self.been[temp1] = 1
            return 1
        seen = set()
        for i in range(level, len(chars)):
            if chars[i] in seen:
                continue
            chars[level], chars[i] = chars[i], chars[level]
            h = self.helper(level + 1, chars)
            if h == 1:
                return 1
            chars[level], chars[i] = chars[i], chars[level]
            seen.add(chars[i])
        return 0
    
    def reorderedPowerOf2(self, N: int) -> bool:
        N = str(N)
        chars = [char for char in N]
        seen = set()
        self.been = {}
        for i in range(0, len(chars)):
            if self.helper(i, chars):
                return True
        return False

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        def backtrack(idx, num):
            if idx==L:
                if num in two_set:
                    return True
                return False
            
            for v in counter:
                if idx==0 and v=='0':
                    continue
                    
                if counter[v]>0:
                    counter[v] -= 1
                    if backtrack(idx+1, num+v):
                        return True
                    counter[v] += 1
            
            return False
            
        perm_set = {N}
        ns = str(N)
        counter = Counter(ns)
        L = len(ns)
        two_set = set()
        num = 1
        while len(str(num))<=L:
            if len(str(num))==L:
                two_set.add(str(num))
            num*=2
        return backtrack(0, '')


import itertools
import math
class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        if N == 1:
            return True
        for i in list(itertools.permutations(list(str(N)))):
            if i[0] != '0'  and int(i[-1]) % 2 == 0:
                num = int(''.join(i))
                # print('i ', i)
                # print('num ', num)
                # print('round(math.log2(num)) ', round(math.log2(num)))
                # print('math.log2(num) ', math.log2(num))
                if bin(num).count('1') == 1:
                # if round(math.log2(num)) == math.log2(num):
                    # print(i)
                    # print(num)
                    return True 
                
        return False
            
    


class Solution:
    pow2 = set()
    for i in range(30):
        pow2.add(''.join(sorted(str(1 << i))))
    def reorderedPowerOf2(self, N: int) -> bool:
        return ''.join(sorted(str(N))) in self.pow2


import itertools
import math
class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        if N == 1:
            return True
        for i in list(itertools.permutations(list(str(N)))):
            if i[0] != '0'  and int(i[-1]) % 2 == 0:
                num = int(''.join(i))
                # print('i ', i)
                # print('num ', num)
                # print('round(math.log2(num)) ', round(math.log2(num)))
                # print('math.log2(num) ', math.log2(num))
                if round(math.log2(num)) == math.log2(num):
                    # print(i)
                    # print(num)
                    return True 
                
        return False
            
    


class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        def is_power_of_two(c):
            return bin(int(''.join(c))).count('1') == 1
        permutations = itertools.permutations(str(N))
        for cand in permutations:
            if cand[0] != '0' and is_power_of_two(cand):
                return True
        
        return False


import itertools
import math
class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        for i in list(itertools.permutations(list(str(N)))):
            if i[0] != '0':  #  and int(i[-1]) % 2 == 0
                num = int(''.join(i))
                # print('i ', i)
                # print('num ', num)
                # print('round(math.log2(num)) ', round(math.log2(num)))
                # print('math.log2(num) ', math.log2(num))
                if round(math.log2(num)) == math.log2(num):
                    # print(i)
                    # print(num)
                    return True 
                
        return False
            
    


from itertools import permutations
class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        
        if N == 1:
            return True
        
        Nstr = str(N)
        pset = set(''.join(p) for p in permutations(Nstr) if int(p[-1])%2==0)
        
        bmk = 1
        while len(str(bmk)) < len(Nstr):
            bmk *= 2
        
        while len(str(bmk)) == len(Nstr):
            if str(bmk) in pset:
                return True
            bmk *= 2
        
        return False        

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        pow_sigs = set()
        twon = 1
        while twon <= 10**9:
            sig = [0] * 10
            s = str(twon)
            for c in s:
                sig[int(c)] += 1
            
            pow_sigs.add(tuple(sig))
            twon *= 2
        
        n_sig = [0] * 10
        s = str(N)
        for c in s:
            n_sig[int(c)] += 1

        if tuple(n_sig) in pow_sigs:
            return True
        else:
            return False

from itertools import permutations

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        
        # Brute force, check every permutation
        res = False
        for n in permutations(str(N)):
            if n[0] == '0':
                continue
            n = int(''.join(n))
            res = max(res, not (n & (n-1)))
            
        return res

import math
from itertools import permutations

class Solution:
    def permutations2(self, N: int) -> List[int]:
        nums = [''.join(p) for p in permutations(str(N))]
        return [int(n) for n in nums if not n.startswith('0')]
    
    def reorderedPowerOf2(self, N: int) -> bool:
        # make permutations of N
        permutations = self.permutations2(N)
        for permutation in permutations:
            if math.log2(permutation).is_integer():
                return True
        return False

class Solution:
    import math
    from itertools import permutations
    def reorderedPowerOf2(self, N: int) -> bool:
        k=str(N)
        a=[x for x in k]
        n=len(k)
        print(a,n)
        ans=list(permutations(k))
        m=0
        #print(ans)
        for i in ans:
            s=''.join(i)
            
            if s[0]!='0' :
                z=math.log(int(s),2)
                if abs(z-int(z))<0.000000001:
                    return True
        
        return False

import math

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        
        if(N==1):
            return True
        
        nn=int(math.log(N)/math.log(2))-1
        tmp=2**(nn)
        
        fun=lambda x: sorted( list(str(x)) ,key=lambda x:int(x),reverse=True)
        N=fun(N)
        
        if(N==fun(tmp)):
            return True
        
    #    print(nn,tmp)
        for x in range(nn,20*nn):
            tmp=tmp*2
            if(N==fun(tmp)):
                return True
            if(nn<len(str(tmp))):
                break
        
        tmp=2**(nn)

        for x in range(nn,nn//20,-1):
            tmp=tmp//2
            if(N==fun(tmp)):
                return True
            if(nn<len(str(tmp))):
                break
        return False
        
        
        
            
        
        
        
        
        
            
        
        
        
        


class Solution:
    def reorderedPowerOf2(self, N):
        c = sorted(str(N))
        for i in range(32):
            if sorted(str(1 << i)) == c:
                return True
        return False

from typing import List


class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        def trans(i) -> List[str]:
            res = []
            while i > 0:
                res.append(i % 10)
                i = i // 10
            return sorted(res)

        for i in range(31):
            if trans(N) == trans(1 << i):
                return True
        return False



from collections import Counter
class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        curr = 1
        N = str(N)
        while len(str(curr)) <= len(N):
            if len(str(curr)) == len(N):
                if Counter(str(curr)) == Counter(str(N)):
                    return True
            curr *= 2
        return False