Sqrt(x)

Easy

Given a non-negative integer n, return the integer square root of n (the floor of the true square root). Do not use built-in sqrt.

Example 1

Input:  n = 4
Output: 2

Example 2

Input:  n = 8
Output: 2
Explanation: floor(2.828...) = 2.

Constraints

• 0 <= n <= 2^31 - 1