069.Sqrt(x)

Posted on | In

Solution 1: accepted

Binary search. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int mySqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1;
    int right = Integer.MAX_VALUE;
    while (true) {
        int mid = left + (right - left)/2;  // prevent integer overflow
        if (mid > x/mid) {                  // prevent integer overflow
            right = mid - 1;
        } 
        else {
            if (mid + 1 > x/(mid + 1))      // prevent integer overflow
                return mid;
            left = mid + 1;
        }
    }
}

Solution 2: accepted

Newton method. Can also be used on other polynomial equations (please save my poor math).
Mathmatical reference: http://www.matrix67.com/blog/archives/361 

1
2
3
4
5
6
7
public int mySqrt(int x) {
    long root = x / 2 + 1; // without 1, test case 1 will always be smaller than 1
    while (root * root > x) {
        root = (root + x / root) / 2; 
    }
    return (int)root;
}