Factorials and Trailing Zeros

Here’s a seemingly impossible and odd query that I’ve been asked in a technical interview:

Question: “How many trailing zeros are there in 126! (factorial)”

At the time I was left stumped and made sure to find out the solution later - so here it is! It turns out there’s a simple solution that works for all numbers.

Answer: 

Firstly, as a quick reminder, a factorial is the product of an integer and the integers below it. For 126! it is: 126 * 125 * 124 * … 3 * 2 * 1

Which can be shown as: n * (n – 1) * (n – 1) * …

Now the solution. The simplest way has three steps, i.e. for number n:

1. Divide the number n by 5 and write down the quotient. Ignore remainders (if any).
2. Then divide the quotient by 5 again and again till you get a quotient less than 5.
3. Add up all the resultant quotients to get the number of zeros in n!

Therefore, for 126! We get to the answer via:

126 / 5 = 25 (Actually 25.2 but we ignore the fraction. Note that 125 / 5 gives us the whole number of 5 – this will be useful in a moment)

25 / 5 = 5

5 / 5 = 1

25 + 5 + 1 = 31 zeros in 126!

This pattern can be shown as:

[ ] indicates only whole numbers; neglect any fractional part in the division process. This pattern may make more sense when we note that 52 is 25 and 53 is 125. The formula technically goes on till infinity but fractions are considered as 0 so do not affect the final result.

For 126! This resulted in [25] + [5] + [1] = 31.

Why does this work? Well, here’s an explanation: We know that a number gets a zero at the end of it if the number has 10 as a factor, e.g. 10 is a factor of 20, 150, and 99990. Also, 5 * 2 = 10, so we need to account for all the products of 5 and 2. However, every other factor is even, so there are far more factors of 2 than 5 - As such, we have to count the number of factors divisible by 5. To phrase it differently, there are many more numbers that are multiples of 2 (2, 4, 6, 8, 10, 12, 14, ...) than are multiples of 5 (5, 10, 15, ...). If we were to take all the numbers with 5 as a factor, we'll have way more than enough even numbers to pair with them to get factors of 10 (and another trailing zero on the factorial). Finally, we need to consider numbers which are factors of 5 and count them again, e.g. 25 (which is 5 * 5 or 52), 125 (5 * 5 * 5 or 53), 625 (5 * 5 * 5 * 5 or 54) etc.

To conclude, here is 126! in full (feel free to count the trailing zeros):

23721732428800468856771473051394170805702085973808045661837377170052497697783313457227249544076486314839447086187187275319400401837013955325179315652376928996065123321190898603130880000000000000000000000000000000

The approximate value is: 2.37217324288E+211

Cleaner code - Comments

I truly believe that if the code is written well enough, comments should not be required at all. Not all comments are bad. They can be useful, i.e. they add additional details, information, caveats or provide example inputs (e.g. good/bad inputs for complex regex). Sadly, most of the time comments are put in with little thought, added automatically and are not kept up to date. It has become a bug-bear of mine and this nonsense has to stop! The following are the types of comments that bug me the most!

Bad comments

Comments should be informative, explain the intent or clarify what the code is doing. Sadly this is not always the case. Please be on guard to remove these variances of bad commenting:

Journal comments

We don't need to document when code was created, last updated or by whom. That's what versioning systems are for.

* Changes (from 11-Oct-2001) * -------------------------- * 11-Oct-2001 : Re-organised the class and moved it to new package *               com.jrefinery.date (DG); * 05-Nov-2001 : Added a getDescription() method, and eliminated NotableDate *               class (DG); * 12-Nov-2001 : IBD requires setDescription() method, now that NotableDate *               class is gone (DG);  Changed getPreviousDayOfWeek(), *               getFollowingDayOfWeek() and getNearestDayOfWeek() to correct *               bugs (DG);

Attributions and Bylines

/* Added by Rick */

Thanks Rick. Remove anything like this.

Noise / Redundant comments

Sometimes you see comments that are nothing but noise. They restate the obvious and provide no new information.

/**   * Returns the day of the month.   *   * @return the day of the month.   */  public int getDayOfMonth() {    return dayOfMonth; }

Consider what purpose does the comment serve. If it’s not more informative than the code, remove.

Misleading comments

These are possibly the worst kind as they may state a fact about the code that may have been true once but is now false. Too often the comments get separated from the code they describe and become orphaned blurbs of ever-decreasing accuracy.

JavaDocs in Nonpublic code

Javadocs are useful for public APIs. Generating Javadoc pages for the classes and functions inside a system is not generally useful, and the extra formality of the Javadoc comments amounts to little more than a distraction. Comments like this just clutter up the code, propagate lies, and lend to general confusion and disorganization.