Sqrt(x)

Given a non-negative integer x, return the integer square root of x (i.e. floor(sqrt(x))) without using a built-in power/sqrt function.

Example

Input: 8 Output: 2 (since 2² = 4 ≤ 8 < 9 = 3²)

Approach

Binary search over the answer space [0, x]: for a candidate mid, check if mid * mid <= x. Find the largest such mid.