Integer Square Root — Solution & Editorial

Back to the Problem

Binary search the answer in [0, 10⁹]: mid² ≤ N moves the lower bound up. Floating-point sqrt is off by one near 10¹⁸.

Complexity: O(log N)