Algo #118: Trailing Zeros in a Factorial

Problem Statement : 
    Find the total trailing zeros in factorial of a number

Example :
Input : 5
Output = 1
Explanation:
  5! = 120 , clearly 1 trailing zero.

Solution : 
   Simple method is to calculate factorial and count number of zeros, but here calculating factorial value would overflow for larger numbers.

We can do better than this approach, since we just have to calculate the trailing zeros and we need not calculate the factorial of the number, factorial can be obtained by multiplying prime numbers and prime number 2 and 5 produces product 10.

Therefore , if we count total number of 5's we are done because we can see 2's are always in excess.
For number like 5, 10 ,15 ... they have only single 5 in them,
but for numbers like 25, 50,25 , they have double 5's in them
Similarly for numbers like 125, 250,375 will have triple 5's in them.

Therefore totals number of 5's which also equal to trailing zeros of n!
       = n/5 + n/(5^2) + n/(5^3) + .....

1 2 3 4 5 6 7

private static int trailingZeroCount(int num) { int count = 0; if(num > 0) for(int i=5;i>=1;i*=5) count += num / i; return count; }

Input : 33
Output : 7

Please comments and post suggestions if any :)
Happy Coding :)