Tell me the logic of the FCTRL program in easy section.

general
1

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

2

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: SPOJ/FCTRL.c at master · Ouditchya/SPOJ · GitHub

3 Likes
3

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…

5 Likes
4

@imcode,

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,

Bruno

3 Likes
5

thanks for the help.

6

thanks…your post helped me understand the logic