192. Factorial Trailing Zeroes

Prompt

Given an integer n, you have to return how many trailing zeroes there are for its factorial value:

n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

For instance, if n = 3, then the output should return 0 because 3! is 6 which has 0 trailing zeroes. However, if n = 5, then the output should return 1 because 5! is 120 which has 1 trailing zero.

The problem prompt also mentions that n could be a number between the range 0 and 10000 inclusive, which is one of the reasons why they are requesting for you to come up with a logarithmic algorithm because a test case might state that n is 10000 (and in case if you are curious, the factorial of 10000 can be found here: https://coolconversion.com/math/factorial/What-is-the-factorial-of_10000_%3F).

Approach

You might be thinking to yourself that we know an integer has a trailing zero if it’s divisible by or a multiple of 10. For instance, 5! is 120 and 120 is a multiple of 10. The problem with this logic is that if we break up 5! in the following way according to the factorial definition:

5! = 5 x 4 x 3 x 2 x 1

There is not a single 10 listed in any of the terms when calculating 5! but we did end up with a trailing 0 when calculating the factorial of 5. How is this possible?

Well, 10 can be broken down further in the sense that 2 x 5 = 10. Furthermore, we do see 2 & 5 both listed among the terms when calculating 5!. It’s important to be careful though that we want to count the number of times 5 appears instead of 2 because a chance that a number is a multiple of 2 is quite high. For instance, if we take the same example of 5!, 4 can be broken down further into 2 x 2:

5! = 5 x (2 x 2) x 3 x 2 x 1

As you can see, there are three 2s and one 5 and we know that 5! factorial equates to 120; therefore, it makes more sense to count the number of 5s among the terms as opposed to 2s.

Let’s calculate the factorial of 25. 25! is 15511210043330985984000000 and it has 6 trailing zeroes. That’s a bit odd according to what we just discussed because normally, we assumed that we could just divide n by 5 and see how many times n is divisible by 5 to determine how many trailing zeroes there are, right? Let’s deconstruct 25! and break it into terms as follows:

25! = 25 x 24 x 23 x 22 x 21 x 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

We can break down the individual terms that are divisible by 5 even further:

  1. 25 = 5 x 5
  2. 20 = 5 x 4
  3. 15 = 5 x 3
  4. 10 = 5 x 2
  5. 5 = 5 x 1
25! = (5 x 5) x 24 x 23 x 22 x 21 x (5 x 4) x 19 x 18 x 17 x 16 x (5 x 3) x 14 x 13 x 12 x 11 x (5 x 2) x 9 x 8 x 7 x 6 x (5 x 1) x 4 x 3 x 2 x 1

If you count the number of 5s that appears, 5 appears six times rather than five times which matches how many trailing zeroes 25! does have.

It’s important to account for this edge case when writing up your code.

Code

Python

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com