Integer Square Root
Easy · binary search
Given a non-negative integer x, return its square root rounded down to a whole number. That is the largest integer r such that r * r <= x.
Do not use a built-in square root, power or floating-point function: the result must be exact for every input.
Examples
Example 1
Input: x = 17
Output: 4
4 * 4 = 16 is at most 17, but 5 * 5 = 25 is too big, so the answer is 4.
Example 2
Input: x = 36
Output: 6
36 is a perfect square, 6 * 6 = 36.
Example 3
Input: x = 0
Output: 0
0 * 0 = 0.
Constraints
- 0 <= x <= 2^31 - 1