Leetcode 69: Sqrt(x)

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

Sqrt(x)

Total Accepted: 68881 Total Submissions: 291203 Difficulty: Medium

Implement int sqrt(int x).

Compute and return the square root of x.

 

Code

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            return -1
        
        left, right = 0, x
        while left <= right:
            mid = left + (right - left)/2
            if mid**2 < x:
                left = mid + 1
            elif mid**2 > x:
                right = mid - 1
            else:
                return mid
        
        return left-1    
        

 

Idea

Binary Search

Leave a comment

Your email address will not be published. Required fields are marked *