424. Square Root Using Binary Search

Given a non-negative integer x, return the floor of its square root (i.e., the largest integer r such that r*r <= x). Do not use built-in exponent functions. Solve in O(log x).

Input: A non-negative integer x.

Output: Floor of square root of x.

Examples

Input: 8
Output: 2
Explanation: sqrt(8)≈2.828. Floor is 2. 2²=4≤8 and 3²=9>8.

Input: 16
Output: 4
Explanation: sqrt(16)=4 exactly. 4²=16≤16.

Input: 0
Output: 0
Explanation: sqrt(0)=0.

Constraints

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

Asked by