C++: Could someone help me optimize my solution?

Question

Program adds 2 fractions and displays their sum in a reduced form (n times). Could someone help me optimize my solution (According to SPOJ, the time limit has been exceeded)

My solution:

#include <iostream>
using namespace std;

int main()
{
    int n, a, b, c, d, gcd;
    long long num, den;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a >> b >> c >> d;
        num = (a*d)+(b*c);
        den = b*d;
        for(int j = 1; j <= num && j <= den; ++j)
        {
            if(num % j == 0 && den % j == 0)
            {
                gcd = j;
            }
        }
        cout << num/gcd << " " << den/gcd << endl;
    }
}

It helps to include the full problem statement, with all relevant details, including the problem bounds. Additionally, if you need to find the GCD, then you can use the standard library's implementation `std::gcd(m, n)`. Finally, online judges are particular about input, and the `iostream` library can be slow if you do not include `std::ios_base::sync_with_stdio(false)` and `cin.tie(nullptr)`. You should also avoid using `std::endl` as it flushes the buffer. Alternatively, you can use `printf()` and `scanf()` which are very fast. — badfilms, Sep 14 '21 at 06:48
@badfilms Everything about `iostream` is in that case micro-optimizations. If an online judge is complaining about that then it is a bad complaint in most cases. If you get a time limit that has been exceeded then this is is normally about doing a naïve brute force approach for solving the problem and a better algorithmic approach has to be found. — t.niese, Sep 14 '21 at 07:00
Look up a faster [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) algorithm, testing every possibility is definitely not the fastest way. One simple optimisation would be to reverse the order of your `j` `for` loop and `break` when you find a value — Alan Birtles, Sep 14 '21 at 07:00
@badfilms and if you suggest to use `std::ios_base::sync_with_stdio(false)` and/or `cin.tie(nullptr)` you should also for example link to [Significance of ios_base::sync_with_stdio(false); cin.tie(NULL);](https://stackoverflow.com/questions/31162367) which gives more details about what impacts those will have. — t.niese, Sep 14 '21 at 07:06

score 1 · Answer 1 · answered Sep 14 '21 at 07:05

The key step in your code is computing the greatest common divisor of num and den. The code does this by testing every number less than or equal to either of them to find the largest that divides both. While this is a correct algorithm, it is very slow, requiring time proportional to whichever is smaller.

To make this faster, use the Euclidean algorithm, which takes time proportional to the logarithm of the smaller number, which means it is much faster. The essence of this algorithm is to divide one number by the other and replace the larger with the resulting remainder until that remainder is zero. Concretely, copying and slightly reformatting the code from tutorialspoint.com:

int gcd(int a, int b)
{
   if (b == 0)
       return a;
   return gcd(b, a % b);
}

Alternatively, as noted in a comment by @badfilms, C++17 contains std::gcd in the library.

C++: Could someone help me optimize my solution?

1 Answers1