FCTRL
/*
|
|
| #include <iostream> |
| using namespace std; |
| int main() |
| { |
| // your code goes here |
| int f=9; |
| do{ |
| int n; |
| cin>>n; |
| int fac=1; |
| for(int i=1; i<=n; i++) |
| { |
| fac= fac*i; |
| } |
| int cont=0; |
| while(fac%10==0) |
| { |
| cont++; |
| fac= fac/10; |
| } |
| cout<<cont; |
| }while(f==9); |
| return 0; |
| } |
| /*Okay, so traditionally I thought this would work but it didn't. |
| There are a bunch of mistakes with this approach. Number one being the infinite loop of the outer do while. And two this program has a definite way of solving it. A traditional method. |
| The traditional method directly calculates the factorial and the trailing zeros in one go. This above method, although its coherent isn't effective. Integer variables have the stress capacity of babies. |
| So, basically this method is pretty much shit for bigger numbers. And I even found people crying about it. I cried with them. |
| https://discuss.codechef.com/t/fctrl-editorial/8651 |
| Let's discuss the traditional method |
| This is the math behind it: https://www.purplemath.com/modules/factzero.htm |
| That's why your coding journey probably starts here. And most importantly my coding journey starts right here too. That link looks pretty complicated and it didn't really make sense to me and I think it still doesn't to actual coders out there. |
| The guy who wrote a solution commented that it was just an algorithm and it was meant to be followed. https://www.thecrazyprogrammer.com/2016/05/count-trailing-zeros-factorial-//number.html |
| So, what's the solution and how to make sense of it?*/ |
| #include <iostream> |
| #include <cmath> |
| using namespace std; |
| int main() |
| { |
| int testcases,i,input,zeroes,c;//Declare all to be integers because we want decimals to be truncated after division. |
| cin>>testcases; |
| for(i=0;i<testcases;i++) |
| { |
| zeroes=0; |
| cin>>input; |
| c=5; |
| while((input/c)>0)//(input/c) is a non negative integer. |
| { |
| zeroes=zeroes+(input/c); |
| c=c*5; //Divide input by a higher power of 5 |
| } |
| cout<<zeroes<<"\n"; |
| } |
| } |
| /*So, first off "testcases" something we all didn't know existed in the program i.e. me and those who cried. That solves one problem: our infinite loop. If they had written the programs question specifically stating this fact, I guess we would've done it. |
| Move on to the while loop, and your input divided by 5 needs to be greater than zero. |
| Then we have zeroes=zeroes+(input/c) and the master line c=c*5. |
| c=c*5 is the master line because this is what checks the number of 5s that the factorial of the number may be composed of. If you even skipped through the math behind this, you must've understood that it doesn't matter about the number of 2s in the factorial, only the 5s matter because in any case they exceed the 2s and pair up to form 10s. |
| Let's say 5 goes in. 5!=5.4.3.2.1=120 thus output=1 |
| while((5/5)>0) { |
| zeroes=0+1; |
| c=5*5; |
| } |
| and the next time we'd get (5/25) practically ending the loop and giving us the output as 1 |
| You could try it for any number, that's humanly possible. And it works like a charm. |
| We divide in powers of 5. And remember how we made them integers. That plays a crucial role too. INTEGERS TRUCATE TO WHOLE NUMBERS. |
| I highly recommend understanding the math once again because all this boils down to is a really neat math trick. Like, a video on 'Multiply 237 and 365 with this Japanese trick in seconds'. |
Comments