Nice C++ O(log n) solution, 11 ms.


  • 0
    C

    First consider the naive solution:
    Start checking from n = 1, 2, .... and find the largest n for which n*n <= x.
    This method will work, but will take O(n) time. The main problem of course is that we step 1 number ahead at a time.

    In order to make this log(n), we have to double our step size at each step. Therefore maintain two guesses (guess, and newguess), with a difference of step between them.

    Keep making new guesses (for increasing step sizes) until newguess*newguess > x. Now we know that our answer lies between guess and newguess.

    However, at this point our step size is too big, and we need better precision (smaller step size) to check between guess and newguess. The solution to this problem lies of course in recursing again, but starting from guess, and with a step size of 1 (which is again doubled at each step).

    class Solution {
        long mySqrt_(long x, long guess) {
            if ((guess*guess) <= x && (((guess+1)*(guess+1)) > x)) return guess;
            long step=1;
            long newguess = guess + step;
            while ((newguess * newguess) <= x) {
                step *= 2;
                guess = newguess;
                newguess = guess + step;
            }
            return mySqrt_(x, guess); //start again with small steps
        }
    public:
        int mySqrt(int x) {
            if (x < 0) return -1; //imaginary number
            if (x == 0 || x == 1) return x;
            return mySqrt_(x, 1);
        }
    };

Log in to reply
 

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