menu

[LeetCode] 069. Sqrt(x)

Problem (Easy)

069. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

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

Example 1:

  • Input: 4
  • Output: 2

Example 2:

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

Approach 1: (My Solution - Primitive, Slow)

Idea

Loop-verify, res*res > x ?

Solution

class Solution1:
    def mySqrt(self, x): 
        """ 
        :type x: int
        :rtype: int
        """
        res = 1 
        while res*res <= x:
            res += 1
        return res-1

Complexity

  • Time: $O(\sqrt{n})$
  • Space: $O(1)$

Approach 1: (My Solution - Binary Search)

Idea

Simple Binary Search between 1 ~ x//2 when x >= 2.

Solution

class Solution2:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 2:
            return x

        left, right = 1, x // 2
        while True:
            mid = left + (right - left) // 2
            if mid > x // mid:
                right = mid - 1
            else:
                if mid + 1 > x / (mid + 1):
                    return mid
                left = mid + 1

Complexity

  • Time: $O(\log n)$
  • Space: $O(1)$



KF

Comments