GCD of n numbers

Question

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;
}

Answer 1

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.