[FIXED] Why does Java integer act erroneously at values near 2^31-1?

Issue

I'm trying to write a Java program to calculate the square root of an integer x, without using in-built functions like Math.pow() . This is the approach I tried -

class Solution {
    public int mySqrt(int x) {
        
        if(x==0 || x==1)
            return x;
        
        // if(x>=2147395600)
        //     return 46340;
        
        int i;
        for(i=1 ; i*i<=x ; i++) {}
        return i-1;
        
    }
}

Without the commented part, I start getting errors if x is in the range 2147395600 <= x <= 2^31-1 (which is the upper limit of an int's value range in Java). For instance, for the input x=2147395600, the expected output is 46340 but the actual output is 289398. Why is this happening? Thanks to all in advance.

PS - I am aware there are other (better) methods to solve this problem, but I'd really like to know why this code behaves this way.

Solution

Since 46340 * 46340 = 2147395600, when i=46340, x=2147395600 and you reach the condition i*i<=x it evaluates to true since 2147395600 = 2147395600. So the loop counter will incremnet by 1 and in the next iteration we will get i=46341 and i * i will cause an overflow - 46341*46341 = -2147479015.
The loop condition will still be true, since -2147479015 <= 2147395600, and the loop will not stop.
You can replace the <= with =, and check for edge cases that may occur now.

Answered By - TDG

Answer Checked By - Marie Seifert (PHPFixing Admin)