Sqrt(x) (LC 69)
Take a whole number x that is 0 or more. Find the largest whole number whose square is at most x: the square root of x with any fractional part thrown away. For x = 8, whose real root is about 2.83, that number is 2.
The problem forbids letting a built-in exponent function or operator do the work, so something like x ** 0.5 in Python or pow(x, 0.5) in C++ is not allowed.
Worked Examples
x = 422 * 2 = 4 fits exactly and 3 * 3 = 9 is too big, so the answer is 2.x = 822 * 2 = 4 fits, but 3 * 3 = 9 is already more than 8, so rounding down gives 2.⚖️Formal Constraints & Bounds
0 <= x <= 231 - 1
Core Insight
The rounded-down root is the last k with k * k <= x. Keep a passing mid with lo = mid and discard a failing mid with hi = mid - 1; round the midpoint up to guarantee progress.
Real-World Scenario & Production Applications
Integer-only code, such as firmware on chips without floating-point hardware or fixed-point graphics, needs an exact integer square root: the side of the largest square grid that fits in x cells, or comparing distances without floats. Python ships this exact function as math.isqrt.
Subproblems & Recurrence Decomposition3 Phases
k * k <= x is True, then False. Search candidates [0, x + 1).
def fits(k): return k * k <= xStep-by-Step Execution Trace Table
For x = 8, pass [0, 9); shift to lo = -1, hi = 8. Probe 4 (False): hi = 3. Probe 1 (True): lo = 1. Probe 2 (True): lo = 2. Probe 3 (False): hi = 2. Return 2. At lo = 2, hi = 3, a floor midpoint would probe 2 and stall; ceiling probes 3.
| 1 | def fits(k): |
| 2 | return k * k <= x |
| 3 | lo = 0 |
| 4 | hi = x + 1 |
| 5 | return binary_search_upper_bound(lo, hi, fits) |
Conceptual Narrative
The rounded-down square root is the largest nonnegative k whose square fits in x. The check k * k <= x reads True, then False, so use Upper Bound to find the last True.
Pass [0, x + 1) to the helper. It shifts both endpoints down by 1 and uses the ceiling midpoint. A passing mid becomes lo; a failing mid makes hi = mid - 1. The answer stays in [lo, hi], and both updates shrink that range.
For x = 8 the answer is 2. A floor midpoint can stall at lo = 2, hi = 3; the ceiling midpoint probes 3 and discards it.
Floor midpoint: With lo = mid, a floor midpoint can equal lo and stall. Round up with + 1.
Keeping a failing mid: Use hi = mid - 1; hi = mid can leave hi unchanged.
Shifting twice: Call the helper with [0, x + 1); it shifts the bounds internally.
Position versus index: bisect_right returns the first greater position, not the last True index.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest whole number whose square is at most x" is a last True: the check k * k <= x gets harder as k grows, so it runs True, ..., True, False, ..., False. "No built-in exponent function or operator" rules out x ** 0.5. The largest value that still passes such a check is Upper Bound, here over the candidates 0 to x.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The check k * k <= x is True up to the answer and False after it. Shift lo and hi down by 1, then use mid = lo + (hi - lo + 1) // 2. Keep a passing mid; discard a failing mid.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Use hi = mid - 1 when the check fails; hi = mid can stall.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I use Upper Bound to find the largest k whose square fits in x. I pass [0, x + 1), and the helper shifts both endpoints down by 1. A ceiling midpoint stays strictly above lo. A passing mid becomes lo; a failing mid makes hi = mid - 1. The last True stays between the bounds, and at equality I return lo. The floor midpoint can stall with lo = mid. This takes O(log(x + 1)) time and
O(1)space.
Complexity & Mathematical Proof
O(log X)
Look at the code: lo, hi = 0, x + 1 starts with X + 1 candidate roots. The Upper Bound template halves the range on every pass of while lo < hi, and each pass calls the check once: one square and one comparison. So there are about log2(X + 1) passes, and the cost is O(log X). The generic blueprint's O(T * log N) becomes O(log X), because T is O(1) here and N = X + 1. A floating-point sqrt would be O(1), but the problem forbids built-in exponent functions such as pow(x, 0.5), so O(log X) integer steps is the bound to aim for here.
O(1)
The code keeps lo, hi and mid (plus the small helper is_feasible), whatever X is, and returns one integer. There is no recursion and nothing is stored per candidate, so the extra space is O(1).
T(X) = T(X / 2) + O(1) = O(log X)
Derivation Progression
O(1)
lo = 0 and hi = x + 1 are constant work.
about log2(X + 1) passes
Each pass of while lo < hi keeps [mid, hi] or [lo, mid - 1], reducing the number of possible answers by about half.
O(1) per pass
One midpoint, one mid * mid, one comparison with x, and one bounds update.
O(log X)
Constant work times a logarithmic number of passes: 31 passes at X = 231 - 1.
Variable Definitions
The input x, from 0 to 2^31 - 1
The candidate root being tested by the Upper Bound loop, lo + (hi - lo + 1) // 2
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): lo, hi, mid
O(1): one integer
Boundary Best / Worst Cases
: there is no early exit, so every x of the same size takes about the same number of passes (tiny inputs also terminate without special cases)
: the largest x needs the most passes
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: the answer is the largest whole number whose square is at most x, and no built-in exponent function or operator may compute it. The largest value that still passes a check that only gets harder is a last True, so the move is Upper Bound over the candidate roots 0 to x. The card shifts the half-open bounds internally and uses a ceiling midpoint to preserve the last True.
, so there are about candidate roots. Budget: time, space. In Java, C# or C++, mid * mid reaches about : square in a 64-bit integer, where it fits, or compare mid == 0 or mid <= x / mid (the division is exact when mid >= 1, and mid = 0 always fits).
Using a floor midpoint with lo = mid can stall. With lo = 2 and hi = 3, it probes 2 and leaves lo unchanged; the ceiling midpoint probes 3. Floating-point shortcuts such as int(math.sqrt(x)) happen to be exact for 32-bit inputs, but for 64-bit inputs a double's 53-bit mantissa cannot hold every integer and the result can round the wrong way; exact integer code searches instead.
Sqrt(x) (LC 69)
Take a whole number x that is 0 or more. Find the largest whole number whose square is at most x: the square root of x with any fractional part thrown away. For x = 8, whose real root is about 2.83, that number is 2.
The problem forbids letting a built-in exponent function or operator do the work, so something like x ** 0.5 in Python or pow(x, 0.5) in C++ is not allowed.
Worked Examples
x = 422 * 2 = 4 fits exactly and 3 * 3 = 9 is too big, so the answer is 2.x = 822 * 2 = 4 fits, but 3 * 3 = 9 is already more than 8, so rounding down gives 2.⚖️Formal Constraints & Bounds
0 <= x <= 231 - 1
Core Insight
The rounded-down root is the last k with k * k <= x. Keep a passing mid with lo = mid and discard a failing mid with hi = mid - 1; round the midpoint up to guarantee progress.
Real-World Scenario & Production Applications
Integer-only code, such as firmware on chips without floating-point hardware or fixed-point graphics, needs an exact integer square root: the side of the largest square grid that fits in x cells, or comparing distances without floats. Python ships this exact function as math.isqrt.
Subproblems & Recurrence Decomposition3 Phases
k * k <= x is True, then False. Search candidates [0, x + 1).
def fits(k): return k * k <= xStep-by-Step Execution Trace Table
For x = 8, pass [0, 9); shift to lo = -1, hi = 8. Probe 4 (False): hi = 3. Probe 1 (True): lo = 1. Probe 2 (True): lo = 2. Probe 3 (False): hi = 2. Return 2. At lo = 2, hi = 3, a floor midpoint would probe 2 and stall; ceiling probes 3.
| 1 | def fits(k): |
| 2 | return k * k <= x |
| 3 | lo = 0 |
| 4 | hi = x + 1 |
| 5 | return binary_search_upper_bound(lo, hi, fits) |
Conceptual Narrative
The rounded-down square root is the largest nonnegative k whose square fits in x. The check k * k <= x reads True, then False, so use Upper Bound to find the last True.
Pass [0, x + 1) to the helper. It shifts both endpoints down by 1 and uses the ceiling midpoint. A passing mid becomes lo; a failing mid makes hi = mid - 1. The answer stays in [lo, hi], and both updates shrink that range.
For x = 8 the answer is 2. A floor midpoint can stall at lo = 2, hi = 3; the ceiling midpoint probes 3 and discards it.
Floor midpoint: With lo = mid, a floor midpoint can equal lo and stall. Round up with + 1.
Keeping a failing mid: Use hi = mid - 1; hi = mid can leave hi unchanged.
Shifting twice: Call the helper with [0, x + 1); it shifts the bounds internally.
Position versus index: bisect_right returns the first greater position, not the last True index.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest whole number whose square is at most x" is a last True: the check k * k <= x gets harder as k grows, so it runs True, ..., True, False, ..., False. "No built-in exponent function or operator" rules out x ** 0.5. The largest value that still passes such a check is Upper Bound, here over the candidates 0 to x.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The check k * k <= x is True up to the answer and False after it. Shift lo and hi down by 1, then use mid = lo + (hi - lo + 1) // 2. Keep a passing mid; discard a failing mid.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Use hi = mid - 1 when the check fails; hi = mid can stall.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I use Upper Bound to find the largest k whose square fits in x. I pass [0, x + 1), and the helper shifts both endpoints down by 1. A ceiling midpoint stays strictly above lo. A passing mid becomes lo; a failing mid makes hi = mid - 1. The last True stays between the bounds, and at equality I return lo. The floor midpoint can stall with lo = mid. This takes O(log(x + 1)) time and
O(1)space.
Complexity & Mathematical Proof
O(log X)
Look at the code: lo, hi = 0, x + 1 starts with X + 1 candidate roots. The Upper Bound template halves the range on every pass of while lo < hi, and each pass calls the check once: one square and one comparison. So there are about log2(X + 1) passes, and the cost is O(log X). The generic blueprint's O(T * log N) becomes O(log X), because T is O(1) here and N = X + 1. A floating-point sqrt would be O(1), but the problem forbids built-in exponent functions such as pow(x, 0.5), so O(log X) integer steps is the bound to aim for here.
O(1)
The code keeps lo, hi and mid (plus the small helper is_feasible), whatever X is, and returns one integer. There is no recursion and nothing is stored per candidate, so the extra space is O(1).
T(X) = T(X / 2) + O(1) = O(log X)
Derivation Progression
O(1)
lo = 0 and hi = x + 1 are constant work.
about log2(X + 1) passes
Each pass of while lo < hi keeps [mid, hi] or [lo, mid - 1], reducing the number of possible answers by about half.
O(1) per pass
One midpoint, one mid * mid, one comparison with x, and one bounds update.
O(log X)
Constant work times a logarithmic number of passes: 31 passes at X = 231 - 1.
Variable Definitions
The input x, from 0 to 2^31 - 1
The candidate root being tested by the Upper Bound loop, lo + (hi - lo + 1) // 2
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): lo, hi, mid
O(1): one integer
Boundary Best / Worst Cases
: there is no early exit, so every x of the same size takes about the same number of passes (tiny inputs also terminate without special cases)
: the largest x needs the most passes
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: the answer is the largest whole number whose square is at most x, and no built-in exponent function or operator may compute it. The largest value that still passes a check that only gets harder is a last True, so the move is Upper Bound over the candidate roots 0 to x. The card shifts the half-open bounds internally and uses a ceiling midpoint to preserve the last True.
, so there are about candidate roots. Budget: time, space. In Java, C# or C++, mid * mid reaches about : square in a 64-bit integer, where it fits, or compare mid == 0 or mid <= x / mid (the division is exact when mid >= 1, and mid = 0 always fits).
Using a floor midpoint with lo = mid can stall. With lo = 2 and hi = 3, it probes 2 and leaves lo unchanged; the ceiling midpoint probes 3. Floating-point shortcuts such as int(math.sqrt(x)) happen to be exact for 32-bit inputs, but for 64-bit inputs a double's 53-bit mantissa cannot hold every integer and the result can round the wrong way; exact integer code searches instead.