Whole-number square root without math.sqrt

Searching sorted data Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
import math
n = 10 ** 30 + 1
print(int(math.sqrt(n)) ** 2 <= n, math.isqrt(n) ** 2 <= n)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True True

Right: both stay at or below n here, though float sqrt can be off for other huge values.

Floating point is risky for very large integers in general, which is why the page's solution searches with exact integer squares.

Why not the others?
  • B False True. Here the float result happens to round to exactly 10¹⁵.
  • C True False. math.isqrt is exact and never overshoots.

30-second answer

Search r in [0, n] for the last value whose square is at most n. Squares grow with r, so the test flips from True to False once. Binary search finds the boundary in O(log n) steps with O(1) space. Python's big integers mean the squares never overflow.

Practise saying it · 30 s. No recording, just a timer

Explain integer square root by binary search.

Say your answer out loud, then check which of these points you covered:

  • Monotonic squares
  • Search last r with r² <= n
  • Round mid up

Deep dive

Searching for 'last True' is the mirror of 'first True': use mid = (lo + hi + 1) // 2 so the range always shrinks.

In fixed-width languages compare mid <= n / mid to avoid overflow.

Newton's method converges faster; binary search is easier to get right in an interview.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def whole_sqrt(n: int) -> int:
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2  # round up so lo = mid always moves
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo

Common mistakes

  • Using (lo + hi) // 2 with lo = mid, which loops forever when hi = lo + 1.
  • Using float sqrt and rounding, which can be off by one for huge n.

Senior take & follow-ups

Point out the 'round mid up' detail when lo = mid; it prevents an infinite loop.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you compute a cube root?

    Show hint

    Same search with r * r * r <= n.

  2. How do you check if n is a perfect square?

    Show hint

    Compute this r and test r * r == n.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.