Сложность: medium
Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.
Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки.
Пример:
Input: n = 1
Output: true
👨💻 Алгоритм:
1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.
2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.
3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.
😎 Решение:
class Solution:
def reorderedPowerOf2(self, N: int) -> bool:
A = list(map(int, str(N)))
return self.permutations(A, 0)
def isPowerOfTwo(self, A) -> bool:
if A[0] == 0:
return False
N = int(''.join(map(str, A)))
return N & (N - 1) == 0
def permutations(self, A, start) -> bool:
if start == len(A):
return self.isPowerOfTwo(A)
for i in range(start, len(A)):
A[start], A[i] = A[i], A[start]
if self.permutations(A, start + 1):
return True
A[start], A[i] = A[i], A[start]
return False
Ставь 👍 и забирай 📚 Базу знаний