Best of CAT (Common Admission Test) - 1

After a relatively refreshing hibernation, I am back to my web log to write a simple terse article, which is the beginning of a series of such articles that deal with some of the best CAT puzzles I encountered. Computational Mathematics - a domain that I am wildly passionate about, is trying to solve these puzzles in both theory and programming. I will start off with a very simple CAT problem that I encountered sometime back. It was rather interesting and deals with Number Theory, which is one of my favorite areas in Mathematics. I transitioned this logic in C++ and it was truly a good exercise.

It is to determine number of zeros in a given number's factorial. Determining the number of zeros in say, 10! is pretty straightforward. But to determine number of zeros in 100! for example is unwieldly - especially from an examination point of view.

Question: What are the number of zeros in 100!

Solution: To determine number of 0's, it is equivalent to determine how many 10's make up the number. For that 10 = 2 x 5 and (2,5) are co-prime. Hence the number of 10's in number N can be determined by N/5 + N/5^2 + N/5^3+ ..... + N/5^n, as long as N/5^n > 1. '^' stands for exponential operator.

=> 100/5 + 100/5^2
=> 20 + 4 = 24.

Answer: 24

I built this into C++ and the code is intuitive.



Click on this code image to enlarge. Also, edit your headers/libs as necessary.

I will keep posting similar problems (especially from CAT) and I believe this would be mutually beneficial.