Integer Square Root

L5 Medium Binary Search

Concept

The square of a non-negative integer is monotonic, so the largest value whose square fits under a target is discoverable by binary search.

Given a non-negative integer x, return the largest integer whose square is less than or equal to x (the integer square root, rounded down). Do not use the built-in sqrt function.

Examples

▸ x = 4

→ 2

▸ x = 8

→ 2

▸ x = 9

→ 3

Progressive Hints

Hint 1 · Nudge

The answer is the largest number whose square still fits, and binary search works because squares grow fast.

Hint 2 · Plan

Set lo = 0 and hi = x and search for the largest mid whose square is at most x. Be careful about overflow, comparing mid against x / mid instead of squaring.

Hint 3 · Approach

lo = 0, hi = x, ans = 0. While lo <= hi: mid = the middle; if mid * mid <= x then ans = mid and lo = mid + 1 else hi = mid - 1. Return ans.

Output

// Run your code to see the output here.