question

The factorial of 10 is 3628800. The last non-zero digit is 8. Write a function to compute the last non-zero digit of (10

^{9}!). Can you calculate (10^{100}!)?
Brute force methods almost never work. Do you really need to multiply every number less than n by each other? Pay attention to the last non-zero digit in your computations.

There are many different ways to solve this problem. I will mention 2 ways - one simple yet inefficient method, and other much more efficient but more complex method.

In the simpler method we can use a brute force approach with some minor modifications to make it much more efficient. To start, implement a simple function that iterates from 2 through n multiplying the iterated number by the total product thus far. Because all we care about is the last non-zero digit for our final result, all we need to store is the last digit during each iteration. So after we calculate our product, using some basic modulus and division operations we can get the last non-zero digit and store it to be multiplied in the next iteration.

A much more efficient method delves into some number theory and relies on the fact that because the number of 2's in the factorial of a number outpace all other digits, the only possible last non-zero digits for factorials are even. Using the prime factorization on n brings out some interesting properties - one such property is that the last digits of the exponents of primes are cyclical. A full explanation of this method has been posted by MathPages. It is quite a long read but I recommend skimming to get the gist of it.

Thoughts or alternate solution? Let us know in the comments below!

In the simpler method we can use a brute force approach with some minor modifications to make it much more efficient. To start, implement a simple function that iterates from 2 through n multiplying the iterated number by the total product thus far. Because all we care about is the last non-zero digit for our final result, all we need to store is the last digit during each iteration. So after we calculate our product, using some basic modulus and division operations we can get the last non-zero digit and store it to be multiplied in the next iteration.

A much more efficient method delves into some number theory and relies on the fact that because the number of 2's in the factorial of a number outpace all other digits, the only possible last non-zero digits for factorials are even. Using the prime factorization on n brings out some interesting properties - one such property is that the last digits of the exponents of primes are cyclical. A full explanation of this method has been posted by MathPages. It is quite a long read but I recommend skimming to get the gist of it.

Thoughts or alternate solution? Let us know in the comments below!