Just use the Newton's method


  • 3
    S
    class Solution {
    public:
        int sqrt(int x) {
            double res = 1;
            while (abs(res/2+x/(2*res) - res) > 0.1) {
                res = res/2+x/(2*res);
            }
            if ((int)res*(int)res > x) res--;
            return (int)res;
        }
    };
    

    This is my code.


  • 0
    L

    what is the runtime complexity?


  • 3
    S

    The convergence rate of the Newton's method is at least quadratic. So I think the complexity is likely to be log. However, we can also use the binary search method to obtain this complexity.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.