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

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Mathematics

Complete search

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:
		return sorted(str(N)) in [sorted(str(1 << i)) for i in range(30)]


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))))
		s = str(n)
		di = dict(Counter(s))
		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
		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))
				if bin(num).count('1') == 1:
					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


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':
				num = int(''.join(i))
				if round(math.log2(num)) == math.log2(num):
					return True
		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:
		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:
		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
		for i in ans:
			s = ''.join(i)
			if s[0] != '0':
				z = math.log(int(s), 2)
				if abs(z - int(z)) < 1e-09:
					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
		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