Two typical solutions in C++, well-explained


  • 2

    Solution

    Binary search

    Directly, we will go to binary search but as for integer sqrt there is one thing should be aware of: sqrt(5)=2 which indirectly gives us hint we should keep the smaller in binary searching but if we do, we will encounter TLE in case 1. As a result, we will not keep the smaller and when we end our searching, we will check it again to return the right value. Besides to avoid overflow, we will use long instead of int.

    Note to avoid infinite loop, we actually should make sure the m will be neither the l nor r when the next half is about l=m or r=m.

    class Solution 
    {
    public:
        int mySqrt(int x) 
        {
            long l = 0, h = x;
            while(l <= h)
            {
                long m = l+((h-l)>>1), t = m*m;
                if(t == x) return m;
                if(t > x) h = m-1;
                else l = m+1;
            }
            return l*l>x? l-1:l;
        }
    };
    

    Newton's method

    This is a math solution which is presented as follows; remember to use long to avoid overflow.
    For more details about methods of computing square roots including Newton's method.

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

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 1
    A

    The binary search method does not work for the input 2147483647, it returns 46341 whereas the expected result is 46340.

    It is a minor issue of the loop condition, instead of while(l<=h) it should be while(l<h)

    Very nice solution, a lot better than my first attempt which went something along the lines of for(int i=1; i*i<x;i++)

    Thanks


  • 0

    @atyagi12 Good point, I've updated it with long now. Thank you.


Log in to reply
 

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