Search code examples
javagreatest-common-divisor

Is this implementation of gcd correct

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.

Solution

  • 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.)