Is this implementation of gcd correct

Question

public static int divisor(int m, int n) {
    if (m == 0 || n == 0) {
        return m+n;
    } else {
        return divisor(n, m%n);
    }
}

It's giving me wrong answers for some input(I don't know which as they don't reveal which input they use for test case) in the amazon.interviewstreet.com

Also why this implementation keeps giving me stackoverflow(again no idea for which inputs)

public static int divisor(int m, int n) {
    if(m == 0 || n == 0) {
        return m+n;
    } else if (m > n) {
        return divisor(n, m%n);
    } else {
        return divisor(m, n%m);
    }
}

Please let me know what am I missing. I'm new to programming and am still a beginner.

I'm sorry that was a typing mistake. I've edited the question. @SotiriosDelimanolis They don't give me explanation for wrong on which specific input so I'm asking that which possible input would produce wrong answers? Maybe that clarifies my question. — meteors, Jul 12 '13 at 07:13

score 1 · Answer 1 · answered Jul 11 '13 at 20:02

1

I think

return(m, n%m);

should be

return divisor(m, n%m);

answered Jul 11 '13 at 20:02

Dan455

352
1
9

I'm sorry that was just a typing mistake, Anyway I submitted with divisor(m, n%m); only. – meteors Jul 12 '13 at 07:10

score 1 · Answer 2 · edited May 23 '17 at 10:25

1

Maybe invalid handling of negative values of n and m? Read e.g. this: Best way to make Java's modulus behave like it should with negative numbers?

edited May 23 '17 at 10:25

Community

1
1

answered Jul 11 '13 at 20:06

score 1 · Answer 3 · answered Jul 11 '13 at 20:12

1

for the second part what is

return(m, n%m);

Is this code get compiled ?

use :

public static int divisor(int m, int n) {
if(m == 0 || n == 0)
    return m+n;
else if(m>n)
    return divisor(n, m%n);
else
    return divisor(m, n%m);}

answered Jul 11 '13 at 20:12

prime

14,464
14
99
131

I've changed the code but what input would cause the code to go into infinite loop(stackOverFlow)? I'm not able to get that. – meteors Jul 12 '13 at 09:40

score 1 · Answer 4 · answered Jul 11 '13 at 20:13

First,

return(m, n%m)

definitely does not compile, I suppose it was meant to be

return divisor(m, n%m);

Second, I guess what is wrong in the second snippet is handling of negative numbers. Because A and B have the same GCD as -A and -B, I would add

m = Math.abs(m);
n = Math.abs(n);

to the beginning of the method

score 1 · Accepted Answer · answered Jul 11 '13 at 20:21

1

I think first one is a code for a programming contest. If so be careful with your data types. May be 'int' is not enough to hold the inputs. Try 'long' instead. (and this will work only if your algorithm is correct.)

answered Jul 11 '13 at 20:21

prime

14,464
14
99
131

Thanks got the answer. Had to use BigInteger instead of ints and long. – meteors Jul 12 '13 at 09:38
post the full code of your program. It will help to understand whats going on. – prime Jul 12 '13 at 19:17
This is the [link](http://pastebin.com/njdfF3Xf) to the code that ended in stackoverflow error previously. – meteors Jul 13 '13 at 06:33
@meteors I add the answer mistakenly to the main question. check that. – prime Jul 14 '13 at 14:55

prime · Answer 6 · 2013-07-13T15:58:36.353

For the second part :

Also why this implementation keeps giving me stackoverflow(again no idea for which inputs)?

Try this input set :

5 3 1 16 5 10

It will give you the stackoverflow error. For your given code in pastebin.

Why ?

If the input is '1' there will be this problem.

edit your code part like below and see the out put for input (1 1).

public static int divisor(int m, int n) {
    System.out.println("### "+m+" "+n);
    if (m == 0 || n == 0) {
        return m + n;
    } else if (m > n) {
        return divisor(n, m % n);
    } else {
        return divisor(m, n % m);
    }
}

in some point out put will be like this :

.
.
### 1 1134903170
### 1 0
### 1 1836311903
### 1 0
### 1 -1323752223
### -1323752223 1
### -1323752223 1
### -1323752223 1
.
.

because in your code the function calling is like below.

   public static int divFib(int num) {
    int i = 1, j = 2, temp;

    while (divisor(num, j) == 1) {
        temp = j;
        j = j + i;
        i = temp;
    }
    return j;
   }

divisor(num, j) will be called like divisor(1, 2) then below part will execute

else {
        return divisor(m, n % m);
    }

the calling will be like divisor(1,0) because n%m = 2%1 =0

then '1' will be return as (m+n = 1).

then while (divisor(num, j) == 1){} will execute again and 'j' will be get increased. But 'num' is '1'. the same thing happens again and again. resulting 'j' to be a huge number and eventually it will assigned a negative number. (I think you know why its happening).

The thing is this will not ever stopped. so the stack will be overflowed due to huge number of function calls.

I think this is a quite clear explanation and if you have any doubt please ask. (Sorry i mistakenly post the answer here.)

But that should be problem in the first implementation too then why it didn't give a stackoverflow error? — meteors, Jul 14 '13 at 15:28
The reason is your first implementation the function calls will return a value after 2 call max. But in your second implementation it there will be huge number of non-returned function calls (which are still in the stack until return a value from the successors ). And that is why your second cade is giving a stack overflow. your first code may give TLE or WA (in the programing contest manner) — prime, Jul 14 '13 at 15:53

Is this implementation of gcd correct

6 Answers6