wayetan
1/5/2014 - 12:45 PM

Sqrt(x)

Sqrt(x)

/**
 * Implement int sqrt(int x).
 * Compute and return the square root of x.
 */
public class Solution {
    public int sqrt(int x) {
        if(x < 0) 
            return -1;
        if(x == 0)
            return 0;
        double y = ((double) x) / 2;
        // y * y - x > 0.00001 ==> y * y != x
        while(Math.abs(y * y - x) > 0.00001){
            y = (y + x / y) / 2;
        }
        return (int) y;
    }
}