Loading…

easyMath GeometryLC #69Frequently asked

Sqrt(x)

Q: How do you solve Sqrt(x) using the Linear Scan approach?

When to use it: Mention briefly as the baseline to establish correctness, then immediately note it's O(√x) and pivot to binary search. The most literal reading: the floor of √x is the largest integer `k` with `k² ≤ x`, so just count up from `1` and stop the moment `k²` exceeds `x`. The last `k` that still satisfied the bound is the answer. **Why this is correct.** The function `k → k²` is strictly increasing on non-negative integers, so there's a single crossover point where `k²` first passes `x`. Everything before it satisfies `k² ≤ x`; everything after fails. Walking upward and stopping at the first failure lands us exactly one past the answer, so we return `k − 1` (or track the last good `k`). **Why it's already overflow-aware.** Even here, `k * k` can overflow as `k` approaches ~46340 and we test one step too far. So we phrase the loop condition as `k <= x / k` rather than `k * k <= x` — the same division trick the optimal solution leans on. This keeps every intermediate value inside 32-bit range. **Why we don't ship it.** O(√x) ≈ 46,000 iterations for the largest input is fast in absolute terms but needlessly linear. Because the predicate `k² ≤ x` is monotonic, we can binary-search the crossover in O(log x) ≈ 31 steps instead. Mention this approach to anchor correctness, then optimize. Time complexity: O(√x). Space complexity: O(1).

LCPractice

Math & Number Theory · 9 of 36 · 8 min

Given a non-negative integer x, return the square root of `x` rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator (such as pow(x, 0.5) or x ** 0.5).

In plain English

Find the largest integer k such that k² ≤ x — that's the floor of the real square root. Since x can be up to ~2.1 billion, its sqrt is up to ~46340, and squaring a candidate near that bound (or beyond) can overflow a 32-bit int, so the comparison must be written to avoid multiplication overflow.

Examples

Example 1

Input: x = 4
Output: 2
Note: √4 = 2, exactly.

Example 2

Input: x = 8
Output: 2
Note: √8 ≈ 2.828, and rounding down gives 2.

Example 3

Input: x = 2147395600
Output: 46340
Note: 46340² = 2147395600 ≤ x, but 46341² overflows a 32-bit int — exactly why we compare with division.

Constraints

0 ≤ x ≤ 2³¹ − 1
x fits in a 32-bit signed integer
No built-in sqrt/pow allowed
Return the floor of √x (integer result)

Clarifying questions4First question: Floor, ceil, or rounded?Explore questions

Q1.Floor, ceil, or rounded?
Floor — the largest integer whose square does not exceed x. sqrt(8) returns 2, not 3.
Q2.Can I use Math.sqrt or pow?
No, the problem forbids built-in exponent functions. That's the whole point — implement it with binary search or Newton's method.
Q3.How large is x?
Up to 2³¹ − 1. That means a candidate's square can overflow a 32-bit int, so compare with division (mid ≤ x/mid) or use a 64-bit type.
Q4.What about x = 0 and x = 1?
Both return themselves: sqrt(0) = 0, sqrt(1) = 1. Make sure the code handles them and never divides by a zero mid.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Return the floor of √x without using a built-in sqrt. Binary-search the answer space [0, x]: for each candidate mid, ask 'is mid ≤ √x?' by testing mid ≤ x/mid (NOT mid*mid ≤ x, which overflows). Converge to the largest integer whose square is ≤ x in O(log x) time.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the answer space is monotonic and binary-searchable, and whether you write the comparison in an overflow-safe way (mid ≤ x/mid) instead of the tempting mid*mid ≤ x.

Where candidates slip

Writing `mid * mid <= x`, which overflows 32-bit int for large x (e.g. x near 2³¹), or computing `mid = (lo + hi) / 2` and overflowing the sum.

How to stand out

Frame it as binary search on the answer, justify monotonicity, use `mid <= x / mid` to dodge overflow, and mention Newton's method as the O(log x) alternative with faster constant factors.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan	`O(√x)`	`O(1)`	Mention briefly as the baseline to establish correctness, then immediately note it's O(√x) and pivot to binary search.	Read
2	Binary Search on the Answer (Optimal)Optimal	`O(log x)`	`O(1)`	The answer they want. Frame it as 'binary search the answer space because mid² ≤ x is monotonic' and call out the overflow-safe comparison.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewInteger floor of √xBuilt-in sqrt allowed?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan

TimeO(√x)SpaceO(1)

Mention briefly as the baseline to establish correctness, then immediately note it's O(√x) and pivot to binary search.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is the largest k with k² ≤ x. What's the simplest way to find it — just try k = 0, 1, 2, … in order?

2Hint 2Explore hint

Increment k until k² first exceeds x. The previous k is your answer (the floor).

3Hint 3Explore hint

This works but does ~√x iterations — up to ~46340 for max x. Fine for small x, but we can do far better with binary search.

A · Core idea

The most literal reading: the floor of √x is the largest integer k with k² ≤ x, so just count up from 1 and stop the moment k² exceeds x. The last k that still satisfied the bound is the answer.

Why this is correct. The function k → k² is strictly increasing on non-negative integers, so there's a single crossover point where k² first passes x. Everything before it satisfies k² ≤ x; everything after fails. Walking upward and stopping at the first failure lands us exactly one past the answer, so we return k − 1 (or track the last good k).

Why it's already overflow-aware. Even here, k * k can overflow as k approaches ~46340 and we test one step too far. So we phrase the loop condition as k <= x / k rather than k * k <= x — the same division trick the optimal solution leans on. This keeps every intermediate value inside 32-bit range.

Why we don't ship it. O(√x) ≈ 46,000 iterations for the largest input is fast in absolute terms but needlessly linear. Because the predicate k² ≤ x is monotonic, we can binary-search the crossover in O(log x) ≈ 31 steps instead. Mention this approach to anchor correctness, then optimize.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 8

k=1

1 ≤ 8/1=8 → ok

Stateans = 1

Final result2

C · Code with teaching comments

Reference implementation previewpublic int mySqrt(int x) { if (x < 2) { return x; } int k = 1;Explore the full code

solution.javaJava

Linear Scan — reference

3 teaching notes

1
public int mySqrt(int x) {
2
    // 0 and 1 are their own square roots and would divide by zero below —
3
    // short-circuit.
4
    if (x < 2) {
5
        return x;
6
    }
7
    int k = 1;
8
    // Overflow-safe form of k*k <= x — division never exceeds 32 bits.
9
    while (k <= x / k) {
10
        k++;
11
    }
12
    // Loop exits one past the floor; back up by one.
13
    return k - 1;
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(√x) timeO(1) spaceOpen the invariant and proofExplore the proof

Even the naive scan should use k <= x / k, not k * k <= x — the overflow trap exists regardless of approach. Establishing the monotonic predicate k² ≤ x here is what justifies binary search next.

ComplexityO(√x) time, O(1) space — We test k = 1, 2, …, √x until the square exceeds x — about √x iterations, each O(1). For x ≈ 2³¹ that's ~46k steps.

E · Edge cases and pitfalls5x = 0 — x < 2 guard returns 0 directly, avoiding division by zero.Explore edge cases

Edge cases handled

x = 0x < 2 guard returns 0 directly, avoiding division by zero.
x = 1x < 2 guard returns 1.

Pitfalls

Writing `k * k <= x` — overflows as k nears 46340.
Dividing by k when k could be 0 — guard x < 2 first.
Returning k instead of k - 1 — off by one at the crossover.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Answer (Optimal)

TimeO(log x)SpaceO(1)

The answer they want. Frame it as 'binary search the answer space because mid² ≤ x is monotonic' and call out the overflow-safe comparison.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The predicate 'mid² ≤ x' is true for small mid and false for large mid — a single monotonic flip. What technique finds that boundary in log time?

2Hint 2Explore hint

Binary-search mid in [0, x]. If mid² ≤ x, mid is a feasible answer — record it and search higher (lo = mid + 1). Otherwise search lower (hi = mid - 1).

3Hint 3Explore hint

Critical: test `mid <= x / mid`, NOT `mid * mid <= x`, to avoid 32-bit overflow. Also compute mid as `lo + (hi - lo) / 2` to avoid overflowing the sum.

A · Core idea

Because k → k² is monotonic, the candidates split cleanly into a feasible prefix (mid² ≤ x) and an infeasible suffix (mid² > x). The floor of √x is the last feasible value — the boundary between the two regions — and finding a monotonic boundary is exactly what binary search does in O(log x).

Searching the answer, not the input. There's no array here. The 'array' we binary-search is the conceptual range of possible answers [0, x]. We pick the middle candidate mid, ask the yes/no question "is mid ≤ √x?", and discard half the range based on the answer. When mid² ≤ x, mid is a valid (possibly-not-maximal) answer, so we record it and push lo = mid + 1 to hunt for something larger. When mid² > x, mid is too big, so hi = mid - 1. The loop ends having recorded the largest feasible mid — the floor.

Why `mid <= x / mid` and not `mid * mid <= x`. This is the crux of the problem. For x near 2³¹, a candidate mid near 46340 has mid * mid ≈ 2.1 billion, right at the 32-bit ceiling — and one step beyond, 46341² ≈ 2.147e9 overflows INT_MAX, wrapping to a negative number and silently corrupting the comparison. Rewriting it as mid <= x / mid is algebraically the same test (divide both sides of mid² ≤ x by mid) but every value stays comfortably within range. The alternative is to widen to a 64-bit long for the product, but the division form needs no wider type at all. Guarding x < 2 up front keeps mid from being 0 in that division.

The other overflow you must dodge. Computing mid = (lo + hi) / 2 can overflow when lo + hi exceeds INT_MAX. Writing mid = lo + (hi - lo) / 2 computes the same midpoint without ever forming the dangerous sum. Two overflow traps, two idioms — interviewers notice when you handle both.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 8

Interactive diagram

Monotonic predicate the search exploits

lo=0, hi=8

Active call / nodeSupporting contextReturned stateNot active

mid² ≤ x is true then false exactly once. Binary search finds that boundary.

Final result2

C · Code with teaching comments

solution.javaJava

Binary Search on the Answer (Optimal) — optimal

4 teaching notes

1
public int mySqrt(int x) {
2
    // 0 and 1 return themselves and keep mid from being 0 in the division below.
3
    if (x < 2) {
4
        return x;
5
    }
6
    int lo = 1, hi = x, ans = 0;
7
    while (lo <= hi) {
8
        // Overflow-safe midpoint — never forms the lo + hi sum that could exceed
9
        // INT_MAX.
10
        int mid = lo + (hi - lo) / 2;
11
        // Overflow-safe form of mid*mid <= x; mid is feasible, so it's a candidate
12
        // answer.
13
        if (mid <= x / mid) {
14
            // Record the largest feasible mid so far — the loop overshoots, this
15
            // preserves the floor.
16
            ans = mid;
17
            lo = mid + 1;
18
        } else {
19
            hi = mid - 1;
20
        }
21
    }
22
    return ans;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(log x) timeO(1) spaceOpen the invariant and proofExplore the proof

Two ideas make this click: (1) binary-search the answer range whenever a monotonic predicate splits it into yes/no halves, and (2) rewrite mid * mid <= x as mid <= x / mid to sidestep overflow without a wider type. That predicate-on-the-answer framing is reusable across Koko Eating Bananas, Split Array Largest Sum, and Capacity to Ship Packages.

ComplexityO(log x) time, O(1) space — Each step halves the search range [0, x], so ~log₂(x) ≈ 31 iterations for max x, each O(1). Only a few scalar variables → O(1) space.

E · Edge cases and pitfalls7x = 2147395600 — mid reaches 46340; 46340 ≤ x/46340 holds, 46341 fails. mid*mid would overflow here — division stays safe. Returns 46340.Explore edge cases

Edge cases handled

x = 2147395600mid reaches 46340; 46340 ≤ x/46340 holds, 46341 fails. mid*mid would overflow here — division stays safe. Returns 46340.
x = 0x < 2 guard returns 0, sidestepping division by zero.
x = 2mid=1 feasible (1 ≤ 2), mid=2 infeasible (2 ≤ 1 false). Returns 1.

Pitfalls

`mid * mid <= x` — overflows for x near 2³¹; use `mid <= x / mid`.
`mid = (lo + hi) / 2` — the sum can overflow; use `lo + (hi - lo) / 2`.
Starting lo at 0 without the x < 2 guard — divides by zero at mid = 0.
Returning lo or hi at the end instead of the recorded ans — off-by-one floor errors.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int mySqrt(int x) { if (x < 2) { return x; } int lo = 1, hi = x, ans = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Squaring mid overflows

For x near 2³¹, mid near 46341 makes mid*mid exceed INT_MAX and wrap negative, corrupting the comparison. Compare with division instead.

Explore the code comparison

Don't write this

if (mid * mid <= x) {
    ans = mid;
    lo = mid + 1;
}

Write this instead

if (mid <= x / mid) {
    ans = mid;
    lo = mid + 1;
}

Midpoint sum overflow

lo + hi can exceed INT_MAX when hi is large (up to x = 2³¹−1). Compute the midpoint without forming the sum.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2;

Write this instead

int mid = lo + (hi - lo) / 2;

Division by zero on mid = 0

If lo starts at 0 and x is 0, mid can be 0 and `x / mid` divides by zero. Guard the x < 2 case and start lo at 1.

Explore the code comparison

Don't write this

lo, hi = 0, x
mid = (lo + hi) // 2
if mid <= x // mid:  # ZeroDivisionError when mid == 0
    ...

Write this instead

if x < 2:
    return x
lo, hi = 1, x

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer

Code pattern to memorize

lo, hi = 0, x
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if mid <= x // mid:   # equivalent to mid*mid <= x, overflow-safe
        ans, lo = mid, mid + 1
    else:
        hi = mid - 1
return ans

Rules to remember

1Compare `mid <= x / mid`, never `mid * mid <= x` — squaring a large mid overflows a 32-bit int. Division stays in range.
2Search the ANSWER, not the input — the candidate sqrt lives in [0, x], and mid² ≤ x is monotonic, so binary search applies.
3Use `mid = lo + (hi - lo) / 2` to avoid lo + hi overflowing for large bounds.
4Track the last valid mid (ans = mid when mid² ≤ x) — the loop overshoots, so the recorded answer is the floor.
5Handle x = 0 and x = 1 — both return themselves; make sure mid is never 0 in the x / mid division (start lo at 1 or guard x < 2).

Use this pattern when

Find the integer floor/ceil of a monotonic function (sqrt, cube root, nth root)
Answer lies in a numeric range and a predicate on it is monotonic
Built-in math functions are disallowed and you need integer precision
'Largest value satisfying a condition' / 'smallest value that breaks it'

Choose another pattern when

A library sqrt is allowed and floating-point precision is acceptable → just call it and floor
You need full floating-point precision, not the integer floor → Newton's method or library
x is tiny and bounded → a simple linear scan is clear enough
The function isn't monotonic → binary search on the answer doesn't apply

Interview takeaway

Sqrt(x) is the entry point to 'binary search on the answer': when you can phrase the problem as 'find the largest k with predicate(k) true' and the predicate is monotonic, binary-search the value range. The overflow-safe `mid <= x/mid` comparison is the detail interviewers look for, and the same template solves Valid Perfect Square, Koko Eating Bananas, and Split Array Largest Sum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary search on the answer space, guarded against overflow. Recognise it whenever you must find the largest/smallest integer satisfying a monotonic predicate without a closed form: integer sqrt, perfect square, Koko Eating Bananas, Split Array Largest Sum. The `mid <= x / mid` rewrite is the reusable overflow-avoidance trick.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Perfect Square
Coming soon
Same binary search, but return whether mid² exactly equals x rather than the floor.
Pow(x, n)
The inverse operation — compute xⁿ in O(log n) via fast exponentiation.
Koko Eating Bananas
Coming soon
Binary search on the answer (eating speed) under a monotonic feasibility predicate.
Find the Smallest Divisor Given a Threshold
Coming soon
Same 'binary search the answer' template with a monotonic sum-of-ceilings predicate.

Same pattern

←

Pow(x, n)

Continue · Next problem

Factorial Trailing Zeroes

easyMath GeometryLC #69Frequently asked

Sqrt(x)

LCPractice

Math & Number Theory · 9 of 36 · 8 min

Given a non-negative integer x, return the square root of `x` rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator (such as pow(x, 0.5) or x ** 0.5).

In plain English

Examples

Example 1

Input: x = 4
Output: 2
Note: √4 = 2, exactly.

Example 2

Input: x = 8
Output: 2
Note: √8 ≈ 2.828, and rounding down gives 2.

Example 3

Input: x = 2147395600
Output: 46340
Note: 46340² = 2147395600 ≤ x, but 46341² overflows a 32-bit int — exactly why we compare with division.

Constraints

0 ≤ x ≤ 2³¹ − 1
x fits in a 32-bit signed integer
No built-in sqrt/pow allowed
Return the floor of √x (integer result)

Clarifying questions4First question: Floor, ceil, or rounded?Explore questions

Q1.Floor, ceil, or rounded?
Floor — the largest integer whose square does not exceed x. sqrt(8) returns 2, not 3.
Q2.Can I use Math.sqrt or pow?
No, the problem forbids built-in exponent functions. That's the whole point — implement it with binary search or Newton's method.
Q3.How large is x?
Up to 2³¹ − 1. That means a candidate's square can overflow a 32-bit int, so compare with division (mid ≤ x/mid) or use a 64-bit type.
Q4.What about x = 0 and x = 1?
Both return themselves: sqrt(0) = 0, sqrt(1) = 1. Make sure the code handles them and never divides by a zero mid.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the answer space is monotonic and binary-searchable, and whether you write the comparison in an overflow-safe way (mid ≤ x/mid) instead of the tempting mid*mid ≤ x.

Where candidates slip

Writing `mid * mid <= x`, which overflows 32-bit int for large x (e.g. x near 2³¹), or computing `mid = (lo + hi) / 2` and overflowing the sum.

How to stand out

Frame it as binary search on the answer, justify monotonicity, use `mid <= x / mid` to dodge overflow, and mention Newton's method as the O(log x) alternative with faster constant factors.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan	`O(√x)`	`O(1)`	Mention briefly as the baseline to establish correctness, then immediately note it's O(√x) and pivot to binary search.	Read
2	Binary Search on the Answer (Optimal)Optimal	`O(log x)`	`O(1)`	The answer they want. Frame it as 'binary search the answer space because mid² ≤ x is monotonic' and call out the overflow-safe comparison.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan

TimeO(√x)SpaceO(1)

Mention briefly as the baseline to establish correctness, then immediately note it's O(√x) and pivot to binary search.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is the largest k with k² ≤ x. What's the simplest way to find it — just try k = 0, 1, 2, … in order?

2Hint 2Explore hint

Increment k until k² first exceeds x. The previous k is your answer (the floor).

3Hint 3Explore hint

This works but does ~√x iterations — up to ~46340 for max x. Fine for small x, but we can do far better with binary search.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 8

k=1

1 ≤ 8/1=8 → ok

Stateans = 1

Final result2

C · Code with teaching comments

Reference implementation previewpublic int mySqrt(int x) { if (x < 2) { return x; } int k = 1;Explore the full code

solution.javaJava

Linear Scan — reference

3 teaching notes

1
public int mySqrt(int x) {
2
    // 0 and 1 are their own square roots and would divide by zero below —
3
    // short-circuit.
4
    if (x < 2) {
5
        return x;
6
    }
7
    int k = 1;
8
    // Overflow-safe form of k*k <= x — division never exceeds 32 bits.
9
    while (k <= x / k) {
10
        k++;
11
    }
12
    // Loop exits one past the floor; back up by one.
13
    return k - 1;
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(√x) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(√x) time, O(1) space — We test k = 1, 2, …, √x until the square exceeds x — about √x iterations, each O(1). For x ≈ 2³¹ that's ~46k steps.

E · Edge cases and pitfalls5x = 0 — x < 2 guard returns 0 directly, avoiding division by zero.Explore edge cases

Edge cases handled

x = 0x < 2 guard returns 0 directly, avoiding division by zero.
x = 1x < 2 guard returns 1.

Pitfalls

Writing `k * k <= x` — overflows as k nears 46340.
Dividing by k when k could be 0 — guard x < 2 first.
Returning k instead of k - 1 — off by one at the crossover.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Answer (Optimal)

TimeO(log x)SpaceO(1)

The answer they want. Frame it as 'binary search the answer space because mid² ≤ x is monotonic' and call out the overflow-safe comparison.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The predicate 'mid² ≤ x' is true for small mid and false for large mid — a single monotonic flip. What technique finds that boundary in log time?

2Hint 2Explore hint

Binary-search mid in [0, x]. If mid² ≤ x, mid is a feasible answer — record it and search higher (lo = mid + 1). Otherwise search lower (hi = mid - 1).

3Hint 3Explore hint

Critical: test `mid <= x / mid`, NOT `mid * mid <= x`, to avoid 32-bit overflow. Also compute mid as `lo + (hi - lo) / 2` to avoid overflowing the sum.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 8

Interactive diagram

Monotonic predicate the search exploits

lo=0, hi=8

Active call / nodeSupporting contextReturned stateNot active

mid² ≤ x is true then false exactly once. Binary search finds that boundary.

Final result2

C · Code with teaching comments

solution.javaJava

Binary Search on the Answer (Optimal) — optimal

4 teaching notes

1
public int mySqrt(int x) {
2
    // 0 and 1 return themselves and keep mid from being 0 in the division below.
3
    if (x < 2) {
4
        return x;
5
    }
6
    int lo = 1, hi = x, ans = 0;
7
    while (lo <= hi) {
8
        // Overflow-safe midpoint — never forms the lo + hi sum that could exceed
9
        // INT_MAX.
10
        int mid = lo + (hi - lo) / 2;
11
        // Overflow-safe form of mid*mid <= x; mid is feasible, so it's a candidate
12
        // answer.
13
        if (mid <= x / mid) {
14
            // Record the largest feasible mid so far — the loop overshoots, this
15
            // preserves the floor.
16
            ans = mid;
17
            lo = mid + 1;
18
        } else {
19
            hi = mid - 1;
20
        }
21
    }
22
    return ans;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(log x) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(log x) time, O(1) space — Each step halves the search range [0, x], so ~log₂(x) ≈ 31 iterations for max x, each O(1). Only a few scalar variables → O(1) space.

E · Edge cases and pitfalls7x = 2147395600 — mid reaches 46340; 46340 ≤ x/46340 holds, 46341 fails. mid*mid would overflow here — division stays safe. Returns 46340.Explore edge cases

Edge cases handled

x = 2147395600mid reaches 46340; 46340 ≤ x/46340 holds, 46341 fails. mid*mid would overflow here — division stays safe. Returns 46340.
x = 0x < 2 guard returns 0, sidestepping division by zero.
x = 2mid=1 feasible (1 ≤ 2), mid=2 infeasible (2 ≤ 1 false). Returns 1.

Pitfalls

`mid * mid <= x` — overflows for x near 2³¹; use `mid <= x / mid`.
`mid = (lo + hi) / 2` — the sum can overflow; use `lo + (hi - lo) / 2`.
Starting lo at 0 without the x < 2 guard — divides by zero at mid = 0.
Returning lo or hi at the end instead of the recorded ans — off-by-one floor errors.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int mySqrt(int x) { if (x < 2) { return x; } int lo = 1, hi = x, ans = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Squaring mid overflows

For x near 2³¹, mid near 46341 makes mid*mid exceed INT_MAX and wrap negative, corrupting the comparison. Compare with division instead.

Explore the code comparison

Don't write this

if (mid * mid <= x) {
    ans = mid;
    lo = mid + 1;
}

Write this instead

if (mid <= x / mid) {
    ans = mid;
    lo = mid + 1;
}

Midpoint sum overflow

lo + hi can exceed INT_MAX when hi is large (up to x = 2³¹−1). Compute the midpoint without forming the sum.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2;

Write this instead

int mid = lo + (hi - lo) / 2;

Division by zero on mid = 0

If lo starts at 0 and x is 0, mid can be 0 and `x / mid` divides by zero. Guard the x < 2 case and start lo at 1.

Explore the code comparison

Don't write this

lo, hi = 0, x
mid = (lo + hi) // 2
if mid <= x // mid:  # ZeroDivisionError when mid == 0
    ...

Write this instead

if x < 2:
    return x
lo, hi = 1, x

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer

Code pattern to memorize

lo, hi = 0, x
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if mid <= x // mid:   # equivalent to mid*mid <= x, overflow-safe
        ans, lo = mid, mid + 1
    else:
        hi = mid - 1
return ans

Rules to remember

1Compare `mid <= x / mid`, never `mid * mid <= x` — squaring a large mid overflows a 32-bit int. Division stays in range.
2Search the ANSWER, not the input — the candidate sqrt lives in [0, x], and mid² ≤ x is monotonic, so binary search applies.
3Use `mid = lo + (hi - lo) / 2` to avoid lo + hi overflowing for large bounds.
4Track the last valid mid (ans = mid when mid² ≤ x) — the loop overshoots, so the recorded answer is the floor.
5Handle x = 0 and x = 1 — both return themselves; make sure mid is never 0 in the x / mid division (start lo at 1 or guard x < 2).

Use this pattern when

Find the integer floor/ceil of a monotonic function (sqrt, cube root, nth root)
Answer lies in a numeric range and a predicate on it is monotonic
Built-in math functions are disallowed and you need integer precision
'Largest value satisfying a condition' / 'smallest value that breaks it'

Choose another pattern when

A library sqrt is allowed and floating-point precision is acceptable → just call it and floor
You need full floating-point precision, not the integer floor → Newton's method or library
x is tiny and bounded → a simple linear scan is clear enough
The function isn't monotonic → binary search on the answer doesn't apply

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Perfect Square
Coming soon
Same binary search, but return whether mid² exactly equals x rather than the floor.
Pow(x, n)
The inverse operation — compute xⁿ in O(log n) via fast exponentiation.
Koko Eating Bananas
Coming soon
Binary search on the answer (eating speed) under a monotonic feasibility predicate.
Find the Smallest Divisor Given a Threshold
Coming soon
Same 'binary search the answer' template with a monotonic sum-of-ceilings predicate.

Same pattern

←

Pow(x, n)

Continue · Next problem

Factorial Trailing Zeroes