Workspace

Problem workspace

3 day streakD

Integer Square Root

EasyBinary SearchNumbers & matrices

The challenge

Return floor(√x), the largest nonnegative integer whose square is at most x.

0 ≤ x ≤ 10⁹. This is an integer search with no floating-point approximation.

Example

x = 26 → 5, because 5² ≤ 26 < 6².

Use the walkthrough below to inspect the input and each state change.

See Floor square root, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchx = 26
left1candidate—right26Search candidate values, not input indices
Tested candidate / qualifying inputResolved positionParameters shown above
Left
1
Middle
—
Right
26
Step 01 / 7

Search the answer range

The candidate is a number, rather than an input index. Keep the largest feasible value.

left = 1; right = 26

Recorded result so far

Not resolved
View exact input

Input: [] · x = 26

Put it into code

Search the last true value of mid² ≤ x. Compare mid ≤ x / mid using integer division to avoid overflowing a product.

Indices are zero-based. C++ uses C++17 or later.

def integer_sqrt(x):
    # 0 <= x <= 10**9
    if x == 0:
        return 0
    left, right, answer = 1, x, 0
    while left <= right:
        mid = left + (right - left) // 2
        if mid <= x // mid:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap