Integer Square Root Floor

Compute floor(sqrt(n)) efficiently without floating-point errors.

math binary-search integer sqrt

Write a function `isqrt_floor(n: int) -> int` that returns the integer square root floor of a non-negative integer n. That is, return the largest integer x such that x * x <= n.

You must compute the result using only integer arithmetic; do not use floating-point operations like `math.sqrt`, `** 0.5`, or any library functions. You may use loops, binary search, or Newton's method, but all calculations must stay in integers.

Examples:
- `isqrt_floor(0)` returns 0
- `isqrt_floor(1)` returns 1
- `isqrt_floor(4)` returns 2
- `isqrt_floor(10)` returns 3 (since 3^2=9 ≤ 10, 4^2=16 > 10)

Implement the function in Python.

Constraints

0 ≤ n ≤ 10^18
Your solution should run in O(log n) time or better using integer operations only.

Example

>>> isqrt_floor(0)
0
>>> isqrt_floor(1)
1
>>> isqrt_floor(4)
2
>>> isqrt_floor(10)
3

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about binary search on the range [0, n].

The condition to check is: does x * x <= n?

For large n, be careful that x * x might overflow in some languages, but Python handles big integers fine.

The answer is the largest integer x that satisfies x*x <= n.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.