[LeetCode Road] Sqrt(x) - Solution/C++

69. Sqrt(x)

Question:

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Example:

Input: x = 4
Output: 2

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2^31 - 1

Source Code

Version 1

Idea:
My intuition is divided divisor that is start from 1, we can get remainder, if remainder is equal to divisor, return the divisor; if divisor is bigger than remainder, retrurn the (divisor - 1).
This method can work, but it wastes much time.

Time complexity: O(sqrt(x))
Space complexity: O(1)

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        int divisor = 1;
        while(divisor <= x){
            int remainder = x / divisor;
            if(divisor == remainder) return divisor;
            if(divisor > remainder) return divisor - 1;
            divisor ++;
        }
        return divisor;
    }
};

Version 2

Idea: We can use binary search to improve time complexity. A variable of l means left index, a variable of r means right index and a variable of m means middle index. l must be set 1, because while(l <= r) can filter x = 0 test case. We use m * m to find which value can match x.

Time complexity: O(logn)
Space complexity: O(1)

class Solution {
public:
    int mySqrt(int x) {
        long l = 1;
        long r = static_cast<int>(x) ;
        while(l <= r){
            long m = (l + r) / 2;
            if ( m * m == x) return m;
            if( m * m > x){
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return r;
    }
};