0

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?

panda
  • 21
  • 3
  • Have you stepped through your code with a debugger? Also, you may want to give [this thread](https://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) a look through. – blackbrandt Jul 28 '22 at 17:45
  • 6
    You are getting the integer overflow. 46341×46341 is larger than 2**31, so it becomes negative and since negative number is smaller than 'x' the loop continues.Consider using long instead of int. – Alex Sveshnikov Jul 28 '22 at 17:50
  • 4
    You could use long, or you could just rearrange the expression: `while (i <= x / i)` instead of using `while (i*i <= x)`. – David Conrad Jul 28 '22 at 18:01
  • Why use `ans`? `while(i*i < x){ i++;}` then return `i`. I'm surprised you get a return value after an integer overflow. – matt Jul 28 '22 at 19:55

3 Answers3

2

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;
}
David Bertrand Neto
  • 21
  • 1
1

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

    public static int mySqrt(int x) {
        int i = 0;
        while (x >= 0) {
            x -= (i++ << 1) + 1;
        }
        return i - 1;
    }
Andrey B. Panfilov
  • 4,324
  • 2
  • 12
  • 18
0

My JavaScript Solution

var mySqrt = function(x) {
var ans = 1;
if(x === 0){
    ans = 0;
} else {
for (let i = 1; i< x;i++){
    if(i*i === x){
        ans = i;
        break;
    }
    if(i*i >x){
        ans = i - 1;
        break;
    }
}
}
return ans;

};

Maaz Khan
  • 1
  • 2