I am trying Leetcode Question - 69. Sqrt(x) Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

class Solution {
    public int mySqrt(int x) {
        int ans = 0;
        
        int i=1;
        while(i*i<=x){
            ans = i;
            i  ;
        }        
        return ans;
    }
}

This is the code I came up with. But the testcase input=2147395600 is not passing.

My Output = 289398 Expected Output = 46340

I'm confused as I have put the condition i*i<=x, then how can ans be more than the sqrt value?

CodePudding user response：

Since you are comparing i * i with the input x, if the input x is too close to Integer.MAX_VALUE (2.147.483.647), like in that test case, i * i will be bigger than the maximum value allowed for an int to have and i*i<=x will be true.

Possible solutions:

1. Implement a binary search algorithm where max would be the floor(sqrt(Integer.MAX_VALUE)) or 46340.
2. Implement a algorithm where ans, i and x are declared locally as long type variables and in the return line you return the value cast to int using return (int)ans;

By running the following algorithm you can see the limit of a java int exploding and what happens afterwards.

int x = 2;
while(true) {
    System.out.println(x);
    x *= 2;
}

CodePudding user response：

Not pretending to be fast, just the idea that (n 1)²=n² 2n 1:

    public static int mySqrt(int x) {
        int i = 0;
        while (x >= 0) {
            x -= (i   << 1)   1;
        }
        return i - 1;
    }