EasyMath & Geometry

Sqrt(x)

Integer square root

Solution Approach

Binary search to find largest integer whose square is <= x. Return floor of square root.

Implementation

def mySqrt(x):
    if x == 0:
        return 0
    left, right = 1, x
    while left <= right:
        mid = (left + right) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    return right

Complexity Analysis

Time Complexity

O(log n)

Space Complexity

O(1)

Complexity

Time:O(log n)

Space:O(1)

Asked at

GoogleAmazon