Finding number of zeros in the end in n! [closed]
Want to improve this question? Update the question so it's on-topic for Stack Overflow.
Closed 11 years ago.
Improve this questionIs there any efficient method to compute the number of zeros at the end of n! without explicitly needing to calculate n!?
Yes there is. Key ideas: (1) it's the same as the highest power of 5 that divides n!; (2) that's the number of multiples of 5 up to n, plus the number of multiples of 25 up to n, plus the number of multiples of 125 up to n, etc.
But this doesn't belong on Stack Overflow.
The number of zeros at the end of N! is given by
∑ floor( n/5i ) for i = 1,2,3....
Simple code in C
i = 1, sum = 0;
while(pow(5,i)<= n)
{
sum += n/(pow(5,i));
i++;
}
The number of zeros in the decimal representation of n! is the number of times ten appears as a factor of that large number. Hence, the number of times 2x5 appears. Hence, as there will be many more occurrences of 2 as a factor than of 5 (why?), it is the number of times 5 is a factor of n!.
So, your interview question is: how many fives appear as factors of items in the expression
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x ... x (n-1) x n
?
精彩评论