# The Precision Hunt

> Some answers need no decimal point.

Canonical URL: <https://datadriven.io/problems/the_precision_hunt>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a non-negative integer n, return the integer part of its square root (floor(sqrt(n))) without using math libraries. Return -1 for negative inputs. Use binary search.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **binary search on a value space** rather than an array. Computing integer square roots without math libraries probes whether candidates can apply binary search to continuous/monotonic functions.

> **Trick to Solving**
>
> Binary search between 0 and n. For each midpoint, check if `mid * mid` is less than, equal to, or greater than n. This narrows the search to O(log n) iterations.

---

### Break down the requirements

#### Step 1: Handle negative input

Return -1 immediately for negative numbers.

#### Step 2: Set up binary search from 0 to n

The square root of n is at most n (and at most n/2 for n above 4, but n is a safe upper bound).

#### Step 3: Narrow the range based on mid squared

If `mid * mid == n`, return mid. If `mid * mid < n`, search higher. If `mid * mid > n`, search lower.

#### Step 4: Return the floor value

When the loop ends, `right` holds the integer part of the square root.

---

### The solution

**Binary search on value space for integer sqrt**

```python
def integer_sqrt(n):
    if n < 0:
        return -1
    if n == 0:
        return 0
    left = 1
    right = n
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        if square == n:
            return mid
        elif square < n:
            left = mid + 1
        else:
            right = mid - 1
    return right
```

> **Time and Space Complexity**
>
> **Time:** O(log n). The search space halves each iteration.
> 
> **Space:** O(1). Only a few integer variables.

> **Interviewers Watch For**
>
> Why return `right` instead of `left` at the end? When the loop exits, `right` is the largest integer whose square does not exceed n, which is the floor of the square root.

> **Common Pitfall**
>
> Using `mid * mid > n` without checking for overflow in languages with fixed-width integers. In Python this is not an issue, but mentioning it shows systems awareness.

---

## Common follow-up questions

- How would you compute the square root to a given decimal precision? _(Tests using floating-point binary search with an epsilon threshold.)_
- What is Newton's method for square roots? _(Tests the iterative formula `x = (x + n/x) / 2` which converges quadratically.)_
- How would you handle very large inputs (e.g., 10^18)? _(Tests that binary search handles this in about 60 iterations.)_
- What if you needed the cube root instead? _(Tests adapting the comparison to `mid * mid * mid`.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_precision_hunt)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.