0069. Sqrt(x)

Easy | Binary Search | 28 ms (96.39%), 14 MB (97.73%)

❓ Problem Statement

Source: LeetCode - Sqrt(x) GitHub: Solution / Performance

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.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

✍🏻 Constraints & Example

Constraints:

• 0 <= x <= 2^31 - 1

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.

💡 Ideas

Binary Search Problem Sorted array to find a minimum number that its power is larger than the input number.

Boundary / Search Space

Left (Minimum) = 1 (first version) Right (Maximum) = x (last element could be the answer)

Condition

While Loop = Left < Right Return = mid * mid == x

Return Value

Left - 1 (square root in integer type means to be smaller or equal to the original number)

🤖 Python3

class Solution:
    def mySqrt(self, x: int) -> int:
        #: (edge)
        if x == 0: return 0
        if x < 4: return 1
        
        # ==================================================
        #  Binary Search + Math                            =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)
        
        l, r = 1, x
        
        while l < r:
            mid = (l + r) // 2
            num = mid * mid
            
            if num == x: return mid
            elif num > x: r = mid
            elif num < x: l = mid + 1
                
        return l - 1

🤖 Java

class Solution {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */

    public int mySqrt(int x) {
        if( x == 0 ) return 0;
        if( x  < 4 ) return 1;
        if( x == 4 ) return 2;
        
        int l = 1, r = x;
        
        while(l < r){
            int mid = l + (r - l) / 2;
            
            // use LONG since mid * mid can be larger than INT.MAX
            long num = (long) mid * mid;
            
            if(num == x) return mid;
            else if(num > x) r = mid;
            else if(num < x) l = mid + 1;
        }
        
        return l - 1;
    }
}