69. Sqrt(x)

Difficulty: Medium

Implement int sqrt(int x)
.
Compute and return the square root of x.

Hide Company Tags
Bloomberg Apple Facebook
Hide Tags
Binary Search Math
Hide Similar Problems
(M) Pow(x, n) (M) Valid Perfect Square

public int mySqrt(int x) {
         if (x == 0)
            return 0;
        //Instead of using fancy Newton's method, this plain binary search approach also works.
        // https://discuss.leetcode.com/topic/8680/a-binary-search-solution
        if (x < 0)  throw new IllegalArgumentException ("x is less than 0");
        int start = 1, end = Integer.MAX_VALUE;
        while (true) {
            int mid = start + (end - start) / 2;
            
            if (mid > x / mid) {
              end = mid - 1;
            } else {
                if (mid + 1 > x /(mid + 1)){
                    return mid;
                }
                start = mid + 1;
            }
        }
    }