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