n! = 1 × 2 × ... × n растёт быстрее любой степени: в 25! уже 26 цифр. Вычислите n! точно и сложите его цифры. Если в языке нет длинной арифметики, храните число как массив цифр и по очереди умножайте его на 2, 3, ..., n.
Реализуйте factorial_digit_sum(n).
Входные данные
n: число, от которого берётся факториал.
Выходные данные
Верните сумму десятичных цифр n!. Обратите внимание, что 0! = 1.
Ограничения
0 ≤ n ≤ 1000
Примеры
Ввод:
n = 5
Ожидаемый вывод:
expected = 3
Ввод:
long long n = 5;
Ожидаемый вывод:
long long expected = 3;
Ввод:
long n = 5;
Ожидаемый вывод:
long expected = 3;
Пояснение
5! = 120, и 1 + 2 + 0 = 3.
Ввод:
n = 0
Ожидаемый вывод:
expected = 1
Ввод:
long long n = 0;
Ожидаемый вывод:
long long expected = 1;
Ввод:
long n = 0;
Ожидаемый вывод:
long expected = 1;
Пояснение
0! по определению равно 1, поэтому ответ 1.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Начните с 1 и умножайте на 2, 3, ..., n.
Подсказка 2
Умножайте каждую цифру, прибавляйте перенос, оставляйте последнюю цифру, а остальное переносите дальше.
Подсказка 3
Если в конце остался перенос, он превращается в новые цифры.
Ожидаемая сложность
время O(n × D), где D - количество цифр в n!, доп. память O(D)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.