Задача: 869. Reordered Power of 2
Сложность: 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 {
    func reorderedPowerOf2(_ N: Int) -> Bool {
        let A = Array(String(N)).map { Int(String($0))! }
        return permutations(A, 0)
    }

    private func isPowerOfTwo(_ A: [Int]) -> Bool {
        if A[0] == 0 { return false }
        var N = A.reduce(0) { $0 * 10 + $1 }
        while N > 0 && (N & 1) == 0 { N >>= 1 }
        return N == 1
    }

    private func permutations(_ A: [Int], _ start: Int) -> Bool {
        var A = A
        if start == A.count { return isPowerOfTwo(A) }
        for i in start..<A.count {
            A.swapAt(start, i)
            if permutations(A, start + 1) { return true }
            A.swapAt(start, i)
        }
        return false
    }
}

Ставь 👍 и забирай 📚 Базу знаний