Сложность: 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 {
public boolean reorderedPowerOf2(int N) {
char[] A = Integer.toString(N).toCharArray();
Arrays.sort(A);
for (int i = 0; i < 30; ++i) {
char[] B = Integer.toString(1 << i).toCharArray();
Arrays.sort(B);
if (Arrays.equals(A, B)) return true;
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний