Problem: Factorial
Tutorial: Trailing Zeros of a Factorial
You are given an integer N, you have to print how many Trailing Zeros N Factorial has.
lets be familiar with the term Factorial. Factorial of a number N is the product of all positive integer less than or equal to N.
Example: 5! = 5*4*3*2*1= 120
Trailing Zeros of a number is the total Zeros the number ends with.
Example: Trailing Zero of 120 is 1,
Trailing Zero of 153 is 0,
Trailing Zero of 50300 is 2.
A number will have a trailing zero if the number has 10 as a factor. that means the number should have 2 and 5 as a factor. if we have a pair of 2 & 5, then we can say that it has a trailing zero. so, trailing zero of a number is the minimum of factors of 2 & 5.
wait..
almost all even number has a multiple number of factor 2.
Example: 6! = 6*5*4*3*2*1. has 2 as factors in 2, 4, 6. but there is only one factor of 5 in number 5.
In the factorial of any number, the number of 2′s as factors will always exceed the number of 5′s as factors. that means, there is enough 2's to be paired with 5's.
now, the problem became easier, the total number of 5's as a factor in an integer is the number of trailing zero of that integer. we just need to count the number of 5's as factor of an integer.
if a number is multiple of 5, then it should have at least one 5's as a factor.
if a number is multiple of 25 (5*5), then it should have at least two 5's as a factor.
if a number is multiple of 125 (5*5*5), then it should have at least three 5's as a factor.
and so on...
lets be clear with an example:
the factorial of number 132 has 132/5^1=26 numbers multiple of 5.
132! has 132/5^2=5 (25, 50, 75, 100, 125) numbers multiple of 5^2
132! has 132/5^3=1 (125) numbers multiple of 5^3.
so factorial of 132 has a total 26+5+1=32 factor of 5's.
we are done, number of Trailing Zeros of 132! is 32.
a little simplification for code to avoid pow function is:
Trailing Zero of 132! = 132/5 + (132/5)/5 + ((132/5)/5)/5 = 26 + 5 +1.
Code
No comments:
Post a Comment