Shubham Sourabhthe room · director's cutplain résumé
Room 04 · The Grind — Binary Search

Sqrt(x)

EASY✓ CHIP-TIMEDLC #69 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Compute the integer square root of a non-negative number — the floor of its true square root, no decimals, no library sqrt calls allowed in spirit.

A single non-negative whole number shows up, and the job is to report the largest integer whose square still fits under it — essentially the floor of the true square root, with no decimal part surviving.

Calling a library square-root function and truncating misses the spirit of this drill; the point is to land on that integer boundary through comparison and search, not through a shortcut function.

Perfect squares resolve exactly, while every other input rounds down to the nearest integer whose square doesn't overshoot — there's no rounding up, ever.

  • input is a single non-negative integer, potentially fairly large
  • the answer is always a non-negative integer, truncated toward zero
  • no built-in sqrt-and-truncate shortcuts — the search itself is the point
  • zero and one are valid inputs and are their own square roots
EX 01
x = 0
→ 0
zero
EX 02
x = 1
→ 1
perfect square, minimum positive
EX 03
x = 4
→ 2
small perfect square

The hintstake only what you need

HINT 1 THE NUDGE

The floor square root of x is the largest integer whose square doesn't exceed x — that's a search over a monotonic yes/no condition, not a formula.

HINT 2 THE STRUCTURE

As guesses increase, guess*guess <= x flips from true to false exactly once. Binary search that boundary directly.

HINT 3 ONE STEP FROM THE ANSWER

Search [0, x] for the largest mid with mid*mid <= x; move lo past mid on a pass, hi before it on a fail, and the answer is the last passing mid.

Coach's boardthe pattern, step by step

THE INTEGER ROOTPATTERN · BINARY SEARCH ON THE ANSWERx = 10
0
1
2
3
4
5
6
7
8
9
10
BEST FLOOR √ SO FAR
— empty —
STEP 1

x = 10. Search the integer range [0, 10] for the largest mid where mid times mid doesn't exceed 10.

STEP 1 / 10 · ← → WORK TOO

The splitstwo paces, two languages

grind/sqrtx.py — RACE PACE
LANG ▸
PACE ▸
class Solution:
    def mySqrt(self, x: int) -> int:
        lo, hi = 0, x
        ans = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans
TIME O(LOG X)SPACE O(1)PYTHON · RACE PACE · 12 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED