The Precision Hunt

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

What is the largest whole number whose square does not exceed n, for the counts our capacity planner hands over, which run far past what a float holds exactly? A negative n has no answer and gets -1.

Some answers need no decimal point.

Example 1

Input:

n = 27

Output:

5

Example 2

Input:

n = 16

Output:

4

Worked solution and explanation

What this one is really asking

This is an exactness problem wearing a math-puzzle costume. Everyone knows how to get a square root. The real question is whether you get the exact floor when n is bigger than a float can represent. The candidate who writes int(n ** 0.5) passes every small example. Then, one below a big perfect square, the float rounds up to the root and the answer comes back one too high. Nothing crashes. It is just wrong.

The version that looks right
def integer_sqrt(n):
    if n < 0:
        return -1
    return int(n ** 0.5)  # off by one near large perfect squares

Correct on every small input, wrong on the hidden large one.

Staying in whole numbers

Step 1: Rule out negatives first

A negative n has no real root, so the guard returns -1 before any arithmetic. Without it, the loop below walks the estimate down to zero and then divides by it.

Step 2: Start from an estimate that is too big

n itself is never smaller than its square root, so start there. Every later estimate stays at or above the true floor, and that is what lets a single comparison decide when to stop.

Step 3: Pull the estimate toward n / estimate

If estimate is too big, n / estimate is too small, and the point halfway between them is a better guess. Written as (estimate * estimate + n) // (2 * estimate), that new guess is computed with one exact integer division, with no rounding anywhere. Far from the root the estimate roughly halves each round; close to it, the number of correct digits doubles each round.

Step 4: Stop once the square fits

The first estimate whose square no longer exceeds n is the floor. The sequence only moves down and never drops below the floor, so there is no off-by-one cleanup at the end.

Exact integer square root
def integer_sqrt(n):
    if n < 0:
        return -1

    estimate = n
    while estimate * estimate > n:
        # midpoint of estimate and n / estimate, floored, all in integers
        estimate = (estimate * estimate + n) // (2 * estimate)
    return estimate
Float then truncate
int(n ** 0.5) is one line and fast, but its precision is capped by the float, so large inputs can come back one too high.
Integer refinement
Every value is an exact integer, so the result is correct for any size of n, at the cost of a short loop.

Common follow-up questions