Can someone please provide me a link to the editorial of FCTRL in easy practice section if at all its there.if it isnt could you tell me the high level logic.thanks
The logic is pretty simple : count the sum of no. of ( num / 5 ), ( num / ( 5^2 ) ),( num / ( 5^3 ) ), etc. till ( num / ( 5^( some n ) ) ) != 0. As we’ll always get an even number smaller than 5^( any no. ) which pairs with this 5^(some no.) to give a ‘0’.
Here’s my code: https://github.com/Ouditchya/SPOJ/blob/master/FCTRL.c
The thing is You have to find no of zeroes at the end of “n!”.I can elaborate on that one…
The Number of zeroes at the end of product a*b depends nearly upon the number of 2’s and number of 5’s when u find prime factors of a and b…
Take an example:
Find number of zeroes behind 105 * 30 * 125->>So find prime factors
105 = 7 * 3 * 5
30 = 2 * 3 * 5 and
125 = 5 * 5 * 5
now neglect Number other than 2 and 5…find powers of 2 and 5 after multiplying all three numbers…
Here we get:->>
2 ^ 1 and 5 ^5
now compare the exponent of 2’s and 5’s power…
Find min(2’s exponent,5’s exponent)…
And thats your answer…
here no of zeroes = min(1,5)=1
Now you can generalise for factorial…
And if u observe carefully it comes out to be above Fromula given by @ouditchya_713…
Hope this concept helps in clearing your doubt…Enjoy…
To understand why this yields the number of zeroes… Think on a smaller problem… When does a number gets a 0 added?
When it’s multiplied by 10 yes?
However there are products which apparentely don’t have 10s but also yield trailing zeroes like:
6x5 = 30
This is because if you decompose 6 in its prime factors you get 2x3 so now you have product:
2x3x5 = 3x10 = 30.
So the only thing you need to do is to find decomposition of every number and count number of factors 2 and 5.
However, there are much, much more numbers with factors of 2 than numbers with factors of 5, which means that the number of zeroes will actually be the number of factors of 5 of N!
Hope this helps,
thanks for the help.
thanks…your post helped me understand the logic