Given a non-negative integer n, return the integer part of its square root (truncating any decimal). Do not use any built-in square root function.
Input
n: a non-negative integer
Output
The largest integer x such that x * x <= n.
Examples
Example 1
Inputn = 16
Output4
Example 2
Inputn = 8
Output2
Explanation: sqrt(8) is approximately 2.83, so the integer part is 2.
Constraints
0 <= n <= 2^31 - 1.