Sqrt(x)

LeetCode Q 69 - Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

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

Example 1: Input: 4 ; Output: 2

Example 2: Input: 8 ; Output: 2
Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.

Solution

Basic idea is to check every number from 1 to n / 2, to see
if ((i * i == x) || (i * i < x) && ((i+1) * (i+1) > x))
We can improve the efficiency by using binary search.

Note that in the code, we can not use condition i * i == x, since this could cause Integer Overflow. So we should use i == x / i.

Code:

public int mySqrt(int x) {
  if (x <= 1) return x;
  
  int left = 1, right = Integer.MAX_VALUE;
  while (true) {
    int mid = left + (right - left) / 2;
    
    if (mid == x / mid) //use mid * mid > x has a potential to cause overflow
      return mid;
    else if (mid > x / mid)
      right = mid - 1;
    else {
      if (mid + 1 > x / (mid + 1))
        return mid;
      left = mid + 1;
    }
  }
}