Легко Решено: 0 Процент решений: 0%

Factorial Digit Sum

Add up the decimal digits of n factorial.

Чему вы научитесь

  • Multiply a digit array by a small number
  • Sum the digits of a large number
  • Remember that 0! = 1

Условие

Показать перевод

n! = 1 × 2 × ... × n grows faster than any power: 25! already has 26 digits. Compute n! exactly and add up its digits. Without big integers, store the number as an array of digits and multiply it by 2, 3, ..., n in turn.

Implement factorial_digit_sum(n).

Input

n: The number whose factorial is taken.

Output

Return the sum of the decimal digits of n!. Note that 0! = 1.

Ограничения

0 ≤ n ≤ 1000

Примеры

Пример 1
Ввод:
n = 5

Ожидаемый вывод:
expected = 3
Ввод:
long long n = 5;

Ожидаемый вывод:
long long expected = 3;
Ввод:
long n = 5;

Ожидаемый вывод:
long expected = 3;

Пояснение

5! = 120 and 1 + 2 + 0 = 3.

Пример 2
Ввод:
n = 0

Ожидаемый вывод:
expected = 1
Ввод:
long long n = 0;

Ожидаемый вывод:
long long expected = 1;
Ввод:
long n = 0;

Ожидаемый вывод:
long expected = 1;

Пояснение

0! is 1 by definition, so the answer is 1.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Start from 1 and multiply by 2, 3, ..., n.

Подсказка 2

Multiply each digit, add the carry, keep the last digit and carry the rest.

Подсказка 3

When the carry is still left over at the end, it becomes new digits.

Ожидаемая сложность

O(n × D) time where D is the digit count of n!, O(D) extra space

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.