GCD of n numbers

The program is supposed to display the GCD of n numbers. I managed to work out the solution, but in only gets 96 / 100 points. Could someone help my oplimize the solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie();
    int n, t;
    std::cin >> n;
    std::cin >> t;
    for(int i = 1; t != 1 && i < n; i++){
        int v;
        std::cin >> v;
        int aux;
        while(v != 0){
            aux = v;
            v = t%v;
            t = aux;
        }
    }
    std::cout << t;
}
Last edited on
c++ has GCD built into it, which is probably faster if the problem is speed.
If not, what exactly do you mean by optimize?

if it is grading by a human:
you did not initialize your variables (line 6 and more )
7 and 8 could be one statement: cin >> n >> t;
4 and 5 are probably not necessary
edge cases:
if t is one, do you get the right answer?
if n is zero, do you get the right answer?
if the user inputs negative numbers, what happens?


Last edited on
The built-in function doesn't seem to solve the problem :( Also, it is not graded by a human. If the t is 1 I do get a right answer, and so do I when the n is zero. The online judge doesn't consider the non-positive numbers. The only thing i know is that 4 out of 100 tests failed
Last edited on
does it work if you upgrade your ints to uint64_t ?
is it possible there are other idiotic cases they threw at you, such as input text when a number is wanted?
Last edited on
Well, the Euclidean algorithm is implemented correctly. There's probably something wrong with how you're reading the input. I don't like that you read at least once even if n is zero.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int gcd = 0; //for when n == 0
std::cin >> n;
for(int i = 0; i < n; i++){
    int input;
    std::cin >> input;
    if (!i){
        gcd = i;
        continue;
    }
    
    int temp;
    while(input != 0){
        temp = input;
        input = gcd % input;
        gdc = temp;
    }
}
Last edited on
Nothing wrong with your solution. Points off for:

Dinking with std::cin unnecessarily. It is not required for the solution.

Nonstandard and/or uninformative variable names. Using good names helps people follow your algorithm. Poor names hinder them.
GCD is usually written using a and b for as argument names, and swap variables are often some variation of "temp".

"aux" is not local to the context where it is used. (It should be inside the loop.)

The GCD could very well be encapsulated as a function, which is invoked from the input loop in main. Separating tasks is very important for understanding and managing one's code. You should be working on this now; future projects just get harder and more complex. Breaking things up into simpler tasks is a required skill.

Honestly, your grade is very generous. You should have lost more points.

Hope this helps.

Last edited on
Topic archived. No new replies allowed.