[Leetcode][python3] 69. Sqrt(x)

problem:

 

code:

# result^2 = x
# x= 2 -> output : 1
# x= 3 -> output : 1
# 4<= x < 9 -> output
# 9<= x < 16 -> output

class Solution:
    def mySqrt(self, x: int) -> int:
        
        # edge case 
        if x==0 : 
            return 0
        
        result =1
        while result*result <= x :
            result += 1
            
        return result-1

 

time complexity

 O(int(root x))

 

 

binary search

# x = 2^30 
# range
# 0 <= result < x
# binary search

class Solution:
    def mySqrt(self, x: int) -> int: #O(int(root x))
        
        #edge case
        if x == 1 :
            return 1
        
        left = 0
        right = x
        while right-left>1:
            approach = int((left+right)/2)
            if approach*approach >x:
                right = approach  
            elif approach*approach < x:
                left = approach
            elif approach*approach == x:
                return approach
        return left

 

time complexity is O(logN)