// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (15 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 20 Solution

Project Euler 20 Solution

Project Euler 20: Find the sum of the digits in 100!


Project Euler 20 Problem Description

Project Euler 20: n! means n × (n − 1) × … × 3 × 2 × 1

Find the sum of the digits in the number 100!

Analysis

This problem can be solved using the same method as used for problem 16 to sum the digits of a very large integer. (See also, Project Euler 16 Solution: )

The solution comes down to one statement that encompasses several steps:

  1. Calculate the factorial (factorial())
  2. and convert it to a string (str()).
  3. Separate the string into single characters and convert back into integer digits (map()),
  4. accumulating them for a sum of the digits for the factorial (sum()).
sum(map(int, str(factorial(N))))

5. Print the result.
The print statement uses placeholders with formatting directives which are filled in with the results following the final ‘%’.

print "Sum of digits for %d! = %d" % ( N, sum(map(int, str(factorial(N)))) )

This program was designed to solve this problem for 100! and the HackerRank version for N! with N ≤ 1000, with up to 100 trials in less than a hundredth of a second.

Trailing zeros in a factorial

You could improve things some if you ignore trailing zeros as they don’t contribute to the sum of the digits. The table below shows how the trailing zeros increase as the factorials become larger. Also, here’s a program that will calculate the number of trailing zeros in a factorial.

Trailing zeros in a factorial
Factorial

# of digits

# trailing zeros

% of length

100!

158

24

15%
1000!

2568

249

9%
10000!

35660

2499

14%
Project Euler 20
This program and method
solves all test cases for
Project Euler 20 on HackerRank

Project Euler 20 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 20 Solution Python 2.7 source.

Afterthoughts

  • Python has inherent support for large integers.
  • The Trinket factorial function doesn’t work for large numbers so we had to create one.

Our factorial function initiates a reduce function to 1 and uses reduce to multiply successive integers from 2 through n to compute a factorial.

def factorial(n): return reduce(lambda x,y: x*y, xrange(2, n+1), 1)
Project Euler 20 Solution last updated

Discussion

No comments yet.

Post a comment