All challenges
Easy 0 solved 0% acceptance

Factorial Digit Sum

Add up the decimal digits of n factorial.

What you'll learn

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

Problem

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.

Constraints

0 ≤ n ≤ 1000

Examples

Example 1
Input:
n = 5

Expected output:
expected = 3
Input:
long long n = 5;

Expected output:
long long expected = 3;
Input:
long n = 5;

Expected output:
long expected = 3;

Explanation

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

Example 2
Input:
n = 0

Expected output:
expected = 1
Input:
long long n = 0;

Expected output:
long long expected = 1;
Input:
long n = 0;

Expected output:
long expected = 1;

Explanation

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

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

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

Hint 2

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

Hint 3

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

Expected complexity

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

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.