Сложность: 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 {
function reorderedPowerOf2($N) {
$A = str_split(strval($N));
sort($A);
for ($i = 0; $i < 30; ++$i) {
$B = str_split(strval(1 << $i));
sort($B);
if ($A == $B) return true;
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний