How to make my code faster?? I am practicing on CodeChef and I am solving a problem. Please see my c-CodePudding

I am a beginner currently in first semester. I have been practicing on Code Chef and am stuck at this problem. They are asking to reduce the execution time of my code. The problem goes as follows: Meliodas and Ban are fighting over chocolates. Meliodas has X chocolates, while Ban has Y. Whoever has lesser number of chocolates eats as many chocolates as he has from the other's collection. This eatfest war continues till either they have the same number of chocolates, or atleast one of them is left with no chocolates. Can you help Elizabeth predict the total no of chocolates they'll be left with at the end of their war?

Input: First line will contain T, number of testcases. Then the testcases follow. Each testcase contains of a single line of input, which contains two integers X,Y, the no of chocolates Meliodas and Ban have, respectively. Output: For each testcase, output in a single line the no of chocolates that remain after Ban and Meliodas stop fighting. Sample Input:

Sample Output:

2
20
8

My code is as follows:

#include <iostream>
using namespace std;

int main() 
{
    unsigned int t,B,M;
    cin>>t;
    while(t--)
    {
        cin>>M>>B;
        if(B==M)
        {
            cout<<B M<<endl;
        }
        else
        {
            for(int i=1;B!=M;i  )
            {
                if(B>M)
                B=B-M;
                else
                M=M-B;
            }
            cout<<M B<<endl;
        }
    }
    return 0;
}

CodePudding user response：

After realizing that your code was correct, I wondered where could be any algorithmic improvement. And I realized that eating as many chocolate from the peer as one has was in fact close to a modulo operation. If both number are close, a minus operation could be slightly faster than a modulo one, but if one number is high, while the other is 1, you immediately get it instead of looping a great number of times...

The key to prevent stupid errors is to realize that if a modulo is 0, that means that the high number is a multiple of the small one and we must stop immediately writing twice the lower value.

So the else part should become:

    ...
    else {
        for (;;) {
            if (M < B) {
                B = B % M;
                if (B == 0) {
                    cout << M * 2 << '\n';
                    break;
                }
            }
            else {
                M = M % B;
                if (M == 0) {
                    cout << B * 2 << '\n';
                    break;
                }
            }
        }
    }
    ...

Note: no infinite loop is possible here because a modulo ensures that for example is M > B > 0' after M = M % Byou will haveB > M >= 0and as the case== 0` is explicitely handled the number of loops cannot be higher than the lower number.

CodePudding user response：

Assuming that Band Mare different from 0, this algorithm corresponds to one version of the Euclidean algorithm. Therefore, you can simply:

std::cout << 2 * std::gcd(B, M) << "\n";

If at least one of the quantity is equal to 0, then just print B M.