Leetcode 0069 Sqrt(x)

Problem statement

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

Solution

We can just start from 1 and increase it. Or we can do binary search.

Complexity

Time complexity of binary serach is O(log n), space is O(1).

Code

class Solution:
    def mySqrt(self, x):
        if x == 0: return 0
        
        beg, end = 1, x
        while end - beg > 1:
            mid = (beg + end)//2
            if mid*mid > x:
                end = mid
            else:
                beg = mid
                
        return beg