Need Help in Understanding of FCTRL ?

general
,
1

Hi,
I solved the problem [FCTRL][1] . My logic is based on finding the number of 5’s in that like

    temp=N/d;
    while(temp>0){
        result=result+temp;
        d=d*5;
        temp=N/d;
    }
Next i checked previous solutions one guy's logic is 
 z = 0;
while(num >= 5) {
num = (num << 1)/10;
z += num;
}

My doubt is how his logic gives write answer even he is calculating 10’s in that number or else can any one please explain his logic mathematically.

Thanks and Regards
Prasad
[1]: http://www.codechef.com/problems/FCTRL

2

number of zeros in n! is min(exponent of 2 in n!,exponent of 5 in n!) ,i.e total numbers of pairs of (2,5)
and in all the cases exp. of 5 is always minimum , so calculating the exp. of 5, or all the pairs of (2,5)
i.e- 2*5=10 , gives the same result

3

the easiest way is to find the sum of
[n/5]+[n/25]+[n/125]…till [] becomes zero.
eg-
60

[60/5]+[60/25]+[60/125]=12+2+0=14
this is a different approach.
it is derived from using n=(2^a)(3^b)(5^c)…
as product ofpower of primes

hope it helps!

4

@prasadram126: That’s easy :wink:

num = (num << 1)/10;

is the same as

num = (num * 2) / 10;

and exactly the same as

num = num / 5;

I have no idea why author wrote it that way, maybe he thought division by 10 is for computer as easy as for human…

1 Like
5

Even that you are correct, your answer is not really related to the question, is it?

6

Even that you are correct, your answer is not really related to the question, is it?

7

i understand that one but in my solution i am multiplying d*5 i.e 5,25,125,… dividing with those ,in his solution every time he is dividing with only 10 how he is getting correct answer that’s what i didn’t understand?

8

As I shown above, he is not dividing by 10, but by 5. And his approach is a little different, but the same at the end. Let say you have 128 as input, you are doing 128/5 + 128/25 + 128/125. What he is doing is

r = 0;
n = 128/5; // new n = 25
r += n; // same as yours
n = n / 5; // old n =25, new n = 5
r += n; // while he divided 128 by 5 before, it's the same as 128/25
n = n / 5 // old n = 25, new n = 1
r += n // n = 1, same as 128/125