Integer Square Root

Write int_sqrt(n) that returns the square root of the whole number n, rounded down: the largest whole number r with r * r <= n.

Do not use math.sqrt, math.isqrt or ** 0.5. The numbers here can have 37 digits, and the answer must be exact.

Examples

int_sqrt(16)   # returns 4
int_sqrt(27)   # returns 5
int_sqrt(0)    # returns 0

27 is not a perfect square: 5 * 5 = 25 fits under it, but 6 * 6 = 36 does not, so the answer is 5.

Constraints

• 0 <= n <= 10^36

Note

Floats keep only about 16 significant digits. int((10**30 - 1) ** 0.5) gives 1000000000000000, one too many: the right answer is 999999999999999. Whole numbers in Python are exact at any size. Counting up from 0 one number at a time would never finish for the biggest inputs, so look for a faster way to close in on the answer.