Easiest way with Newton method


  • 2
    J

    S1:To calculate the square root of the number of x, from the beginning to select an arbitrary guess g;

    S2:If you guess the correct value g is close enough to the square root of the end of the algorithm, the function g as the correct value of the square root, the algorithm ends, the return value of g;

    S3:G If the guess is not accurate enough, with an average value g and g / x as a new guess. Because of these two values is the square root of a less than exact, exact square root is greater than the other, the average will get you select a value closer to the correct answer;

    S4:The new guess stored in the variable g, repeat S2

    Here is the Newton method function:

    X(n+1)=1/2(X(n)+S/X(n))

    class Solution {public:int mySqrt(int x) {    
        double g=x;
        while(abs(g*g-x)>0.000001)
            g=(g+x/g)/2;
        return g;
        }
    };

  • 0
    A

    The solution is OK mathematically. The problem is at an interview they will look to see if you can implement binary search correctly in this case.


Log in to reply
 

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