Easy

Sqrt(x)

043

Given a non-negative integer x, return the integer square root of x. The result should be rounded down to the nearest integer.

EXAMPLES

Example 1

Input
{
  "x": 8
}

Output
2

FUNCTION SHAPE

x: int→int

SOLUTION NOTE

Max template since we want largest mid where mid² <= x. Min template with mid² >= x gives ceiling.

Reveal reference solution +

pythonREFERENCE

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

TimeO(log x)

SpaceO(1)

Open on LeetCode ↗