1
\$\begingroup\$

According to an online judge, the limit has been exceeded. Could someone help me optimize my solution for the Greatest Common Divisor of n numbers:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int t = a[0];
    for(int i = 1; i < n; i++){
        t = __gcd(t, a[i]);
        if(t == 1){
            break;
        }
    }
    cout << t;
}
New contributor
Max W is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
2
  • \$\begingroup\$ Is this really a TLE problem or did the online judge misreport a compilation failure as TLE? \$\endgroup\$
    – harold
    Sep 14 at 19:48
  • 2
    \$\begingroup\$ If this is a programming challenge, it is often helpful to link to the programming challenge. \$\endgroup\$
    – mdfst13
    Sep 14 at 20:45
4
\$\begingroup\$

Avoid non-standard functions

Instead of __gcd(), which is a non-standard function, use std::gcd().

Avoid unnecessarily storing data

There is no reason to first read all data into an array, and then loop over the whole array. You can just process the data while it is being read in:

std::cin >> t;

for(int i = 1; t != 1 && i < n; i++) {
    int v;
    std::cin >> v;
    t = std::gcd(t, v);
}

This has several benefits:

  • No memory allocation (either on stack or on heap) required, so also no possibility to run out of memory.
  • Since there is no array to loop over, there's less memory bandwidth necessary and you have better cache locality.
  • You can stop reading the input once t == 1, whereas originally you would have continued reading in more data.

Avoid using namespace std

Try to avoid using namespace std, it is considered bad practice. And while it can save some typing, shorter code is not necessarily making your code go faster.

\$\endgroup\$

Your Answer

Max W is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.