Сложите все цифры числа n. Если результат — многозначное число, снова сложите его цифры. Повторяйте, пока не останется одна цифра.
Реализуйте функцию digital_root(n).
Ввод
n: Положительное целое число.
Вывод
Верните получившуюся одну цифру.
Ограничения
1 ≤ n ≤ 10¹⁸
Примеры
Пример 1
Ввод:
n = 999
Ожидаемый вывод:
expected = 9Ввод:
long long n = 999;
Ожидаемый вывод:
long long expected = 9;Ввод:
long n = 999;
Ожидаемый вывод:
long expected = 9;Пояснение
9 + 9 + 9 = 27, затем 2 + 7 = 9.
Пример 2
Ввод:
n = 38
Ожидаемый вывод:
expected = 2Ввод:
long long n = 38;
Ожидаемый вывод:
long long expected = 2;Ввод:
long n = 38;
Ожидаемый вывод:
long expected = 2;Пояснение
3 + 8 = 11, затем 1 + 1 = 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Если повторно складывать цифры, число в итоге сведётся к одной цифре.
Подсказка 2
Можно просто повторять сложение, пока значение не станет меньше 10.
Подсказка 3
Следи за очень большими входами: метод простой, но основная работа — это повторные проходы по цифрам.
Ожидаемая сложность
O(d log n) по времени, O(1) дополнительной памяти