Finding number of zeros in the end in n! [closed]

Closed. This ques开发者_运维问答tion is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

Is 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/5ⁱ ) 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

?