Ссылка на задачу - 1780. Check if Number is a Sum of Powers of Three.
📌 Описание задачи
Дано число n. Нужно определить, можно ли представить его в виде суммы различных степеней тройки.
🔹 Пример:
- 📥 Ввод:
n = 12
- 📤 Вывод:
true
- 💡 Объяснение:
12 = 3⁰+3¹+3² = 1 + 3 + 9.
💡 Идея
Рассмотрим представление n в троичной системе счисления:
- Если в записи числа есть цифра
2, то решения нет (так как нельзя взять две одинаковые степени).
- Если в записи есть только
0 и 1, то решение существует (мы просто берём соответствующие степени тройки).
Таким образом, задача сводится к поразрядной проверке числа в троичной системе счисления.
🚀 Детали подхода
Будем использовать рекурсию и деление числа на 3:
- База рекурсии: Если
n == 0, то мы успешно разложили число, возвращаем true.
- Шаг рекурсии: Если
n % 3 == 2, то n нельзя разложить, возвращаем false.
- Рекурсивный вызов: Проверяем
n / 3, повторяя процесс.
⏱ Асимптотика
- Временная сложность:
O(log n), так как n уменьшается в 3 раза за итерацию.
- Пространственная сложность:
O(log n) из-за глубины рекурсии
(несложно алгоритм преобразовать в цикл, чтобы получить O(1)).
📝 Исходный код
impl Solution {
pub fn check_powers_of_three(n: i32) -> bool {
n == 0 || (n % 3 != 2 && Self::check_powers_of_three(n / 3))
}
}
Tags: #rust #algorithms #math