Need Help in Understanding of FCTRL ?

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

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

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!

@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…

2 Likes

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

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

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?

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