Sqrt(x)

EASY✓ CHIP-TIMEDLC #69 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

x = 0

→ 0

ZERO

EX 02

x = 1

→ 1

PERFECT SQUARE, MINIMUM POSITIVE

EX 03

x = 4

→ 2

SMALL PERFECT SQUARE

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

THE HINTS — TAKE 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 BOARD — THE PATTERN, STEP BY STEP

THE INTEGER ROOTPATTERN · BINARY SEARCH ON THE ANSWERx = 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 SPLITS — TWO 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

class Solution {
    public int mySqrt(int x) {
        long lo = 0, hi = x;
        long ans = 0;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid * mid <= x) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return (int) ans;
    }
}

TIME O(LOG X)SPACE O(1)JAVA · RACE PACE · 16 LN

class Solution {
    public int mySqrt(int x) {
        long i = 0;
        while ((i + 1) * (i + 1) <= x) {
            i++;
        }
        return (int) i;
    }
}

TIME O(√X)SPACE O(1)JAVA · TRAINING PACE · 9 LN

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