Skip to main content

Trailing Zeroes of n!

  • Find the number of trailing zeroes in 122! ? 
That's a big number right? The solution is pretty simple. Ask yourself when does any multiplication results in a trailing zero? The answer is (2x5) = 10, leaves one zero behind. The factorial of 122 is a multiplication which you already know. The expansion is,

98750442008336013624115798714482080125644041369
78359605958470050267671457205014364903379642774
50422940710230505796264047365129395968426948958
21378210620013388054747214795243520000000000000
000000000000000


So, we have to find the number of multiples of 5 from the expansion and they are 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120.
So there are 24 multiples of 5.

then again, 25= 5 x 5, which has another extra factor of  5 to count. So how many multiples of 25 from 1 to 122?
(122 / 25) = 4 (taking the only integer)

So, add that 4 to the earlier count. 24 + 4 = 28, so we have 28 trailing zero in 122!

Let's take a number even larger than 122. How about 1001!  ?
 
This time we have to check for multiples of 5, 25 and also 125 ( has extra two factor of 5 ),  625 ( has extra four factors of 5 )

easy calculation: ( 1001 ÷ 5 ) + ( 1001 ÷ 25 ) +  ( 1001 ÷ 125 ) + ( 1001 ÷ 625 )= 200+40+8+1 = 249
So 1001! has 249 trailing zeroes.

This shows a pattern: divide N by powers of 5 until the divisior is greater than N.
and this is a special case of de Polignac's formula .




Labels:

Comments

Post a Comment

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left
14 comments
Read more

SPOJ 4300 - Rectangles

Problem Statement Hint: If the input is 15 squares rectangles are-                 1x1 1x2 1x3 ...................................1x15                        2x2 2x3 ............................2x7                                   3x3   ....................3x5                          can't make 3x2 cause 3x2 and 2x3 are same . can't make 2x8 cause that requires 16 squares. can't make 4x4 cause that also requires 16 square.  Solution: #include<stdio.h> int main() {     int n,c=0,i,j;     scanf("%d",&n);     for(i=1;i*i<= n;i++)     {         c+= (n/i)-i+1;     }     printf("%d\n",c); } * If there's any query or mistake, let me know.
Post a Comment
Read more