Sqrt(x)

Implementint sqrt(int x).

Compute and return the square root ofx, 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

class Solution {
    public int mySqrt(int x) {
        // 1 -> 0
        // 2 -> 0
        // 3 -> 0
        // 4 -> 2
        // 5 -> 2
        // 6 -> 2
        // 7 -> 2
        // 8 -> 
        // 16 -> 4
        // seed = 1
        // result = x / (x / x')
        // loop 0..x -> seed -= (seed * seed - x) / (2 * seed)

        // using stackoverflow
        //int seed = 1;
        //for (int i = 0; i < x; i++) {
        //    seed -= (seed * seed - x) / (2 * seed);
        //}
        //return seed;

        long r = x;
        while (r * r > x) {
            r = (r + x/r) / 2;
        }
        return (int) r;
    }
}