Description

https://oj.leetcode.com/submissions/detail/13480861/

Difficulty: 2.5/5.0

Solution

Here we use Newton Method to solve this problem. Please refer to http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity.

class Solution {
public:
    int sqrt(int x) {
        double est = 1;
        while(fabs(est * est - x) >= 1)
            est = (est + x/est)/2;
        return floor(est);
    }
};