Sqrt(x)

Happy Number

Count Primes

Return the integer square root of a non-negative integer, rounding down to the nearest whole number.

Given a non-negative integer `x`, return the **integer square root** of `x` — the largest integer `r` such that `r * r <= x`. The fractional part is truncated (rounded down), and you must not use any built-in square-root function.

**Input / output**
- Input: `x: integer`
- Output: `floor(sqrt(x))`

**Examples**
1. `x = 4` returns `2`.
2. `x = 8` returns `2` (`sqrt(8) = 2.828...`, truncated to `2`).
3. `x = 0` returns `0`.

**Constraints**
- `0 <= x <= 2,147,483,647`

**Follow-up**
Binary search gives `O(log x)`. Guard the midpoint test against overflow (in fixed-width languages) by comparing `mid` to `x / mid` instead of computing `mid * mid`. Could Newton's method converge faster?

- We want the largest `r` with `r * r <= x`.
- The answer is monotonic: if `r * r <= x`, then every smaller value also qualifies.
- Monotonicity is exactly what binary search exploits.

Understand the Pattern

- For `x < 2`, the integer square root equals `x` itself (`0 -> 0`, `1 -> 1`).
- Returning early avoids an empty search range.

Handle the Small Cases

- Search the range `[1, x]` for the largest `mid` whose square is `<= x`.
- Move the lower bound up when `mid * mid <= x`, otherwise move the upper bound down.
- Track the best valid `mid` as you go.

Binary Search the Root

- The search halves the range each step, so time is `O(log x)`.
- Space is `O(1)`.
- In fixed-width languages, compare `mid` to `x // mid` to dodge `mid * mid` overflow.