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

💡 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