Skip to main content

69. Sqrt(x)

https://leetcode.com/problems/sqrtx/

Python​

Brute Force​

  • Time rank: faster than 13.06%
  • Space rank: less than 97.76%
class Solution:
    def mySqrt(self, x: int) -> int:
        base = 1

        while base * base <= x:
            base += 1

        return base - 1
  • Time rank: faster than 57.22%
  • Space rank: less than 38.71%
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left, right = 2, x//2

        while left <= right:
            pivot = left + (right-left)//2
            num = pivot * pivot

            if num == x:
                return pivot
            elif num > x:
                right = pivot - 1
            else:
                left = pivot + 1

        return right