GCD of n numbers

Sep 18, 2021 at 4:58pm
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 Sep 18, 2021 at 4:58pm
Sep 18, 2021 at 5:57pm
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 Sep 18, 2021 at 6:02pm
Sep 18, 2021 at 7:59pm
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 Sep 18, 2021 at 7:59pm
Sep 18, 2021 at 8:44pm
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 Sep 18, 2021 at 8:46pm
Sep 18, 2021 at 8:47pm
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 Sep 18, 2021 at 8:47pm
Sep 19, 2021 at 1:49am
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 Sep 19, 2021 at 1:50am
Topic archived. No new replies allowed.