Integer Square Root

Compute the floor of the square root of a non-negative integer without using floating-point math.

math integer sqrt binary-search

Write a function `integer_sqrt(n)` that takes a non-negative integer `n` and returns the **floor** of its square root. That is, return the largest integer `x` such that `x * x <= n`.

You must compute the result using only integer arithmetic — do **not** use `math.sqrt`, the `**` operator, or any floating-point operations. You may use any algorithm (e.g., binary search or Newton's method) as long as it is exact for all inputs up to 10^12.

**Function signature:** `def integer_sqrt(n: int) -> int:`

**Examples:**
```python
integer_sqrt(0)   # returns 0
integer_sqrt(1)   # returns 1
integer_sqrt(4)   # returns 2
integer_sqrt(10)  # returns 3 (since 3*3=9 ≤ 10, 4*4=16 > 10)
integer_sqrt(25)  # returns 5
integer_sqrt(26)  # returns 5
```

Constraints

- 0 ≤ n ≤ 10^12
- Time complexity: O(log n) expected (binary search) or equivalent
- Space complexity: O(1)
- The function must use only integer arithmetic; no floating-point or `math` module.

Example

```python
>>> integer_sqrt(0)
0
>>> integer_sqrt(1)
1
>>> integer_sqrt(4)
2
>>> integer_sqrt(10)
3
>>> integer_sqrt(25)
5
>>> integer_sqrt(26)
5
```

8 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of binary search: find the largest x such that x*x <= n.

Set low = 0, high = n (or maybe n//2+1). While low < high, test mid.

Be careful with mid*mid overflow? Python integers are unbounded, so no overflow.

Alternatively, you can use a simple loop but that would be too slow for large n.

Test Results

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