CODEWITHSUNDEEP
javaalgorithm
mitcc
mitcc

Reputation: 343

Euler Project 5 in java, why is there a different result?

/* Smallest multiple */
/*
 * 2520 is the smallest number that can be divided by each
 *  of the numbers from 1 to 10 without any remainder.What 
 *  is the smallest positive number that is evenly divisible 
 *  by all of the numbers from 1 to 20?
 */
public class SmallestMultiple {
    public static int gcd(int m, int n){
        if(n>m){
            int temp = m;
            m = n;
            n = temp;
        }
        int gcdNum = m;
        while(m != 0){
            m = gcdNum%n;
            gcdNum = n;
            n = m;
        }
        return gcdNum;
    }
    private static int lcm(int m, int n){
        return m*n/gcd(m,n);
    }
    static int multiple(int start, int end){
        if(start > end){
            int temp = end;
            end = start;
            start = temp;
        }
        else if(start == end)
            return start;
        else
            return lcm(end, multiple(start, end-1));
        return multiple(start, end);
    }
    public static void main(String[] args) {
        System.out.println(multiple(11,19)); // line a--Which is equal to multiple(1,19) 
        System.out.println(multiple(11,20)); // line b--Which is equal to multiple(1,20)
    }
}

I think the answer multiple(1,19) and multiple(1,20) will get the same result. But with my code, they are different, multiple(1,19)=232792560(the right answer)and multiple(1,20)=18044195 which is the wrong answer!!! I know there is many much more simple algorithms, but I just want to know where is my problem... Who can tell me the problem?

Upvotes: 2

Views: 229

Answers (2)

Sirko
Sirko

Reputation: 74076

Your problem is pretty much just an integer overflow.

The largest intnumber in Java is Integer.MAX_VALUE = 2147483647.

At some point you try to run lcm( 20, 232792560 ). The latter being the result for multiplay(1,19).

Inside your function, you try to compute m*n/gcd(m,n).

With m == 20, n == 18044195 and gcd(m,n) == 20, this gets 20 * 18044195 / 20.

The first product is actually 20 * 18044195 == 4655851200, which is larger than Integer.MAX_VALUE, thus an overflow happens and your total result runs bad.

One solution would be to switch to a long type everywhere, which has a maximum value of Long.MAX_VALUE == 9223372036854775807 .

Upvotes: 2

Daniel Fischer
Daniel Fischer

Reputation: 183888

You have int overflow when you compute

Prelude> 232792560 * 20
4655851200
Prelude> it `quotRem` (2^32)
(1,360883904)

Thus you obtain 360883904 / 20 = 18044195.

You can

  • use long or
  • compute m * (n/gcd(n,m))

to avoid the overflow (the second method won't take you much farther, if the upper limit is 23, int is too small to hold the result).

Upvotes: 3

Related Questions