Sqrt(x)

The fastest way to solve this problem is to stop searching for a square root and search for the last integer that is still feasible.

For a candidate r, feasibility is simple:

r * r <= x

The feasible candidates form one continuous block starting at 0. That structure lets us binary-search the integer answer space and return the greatest feasible candidate.

State the Exact Contract

The input is a non-negative integer x with:

0 <= x <= 2^31 - 1

Return the greatest non-negative integer r whose square is at most x:

r * r <= x

This is the floor square root.

The result is not always an exact mathematical square root:

• x = 4 → return 2, because 2 * 2 == 4
• x = 8 → return 2, because 2 * 2 <= 8 but 3 * 3 > 8

Built-in exponentiation or square-root shortcuts are prohibited. In Python, that rules out expressions such as x ** 0.5 and pow(x, 0.5).

So the real task is:

Find the largest integer r such that r * r <= x.

That wording exposes the binary-search shape.

Recognize the Answer-Space Pattern

This is binary search, but there is no sorted array.

Instead, the possible answers are the integers in a range:

0, 1, 2, 3, ..., x

For each candidate m, define a feasibility predicate:

P(m): m * m <= x

For x = 8, the predicate behaves like this:

m	m * m	P(m)
0	0	true
1	1	true
2	4	true
3	9	false
4	16	false

As m increases, the predicate changes only once:

true, true, true, false, false, ...

That one-way behavior is called monotonicity. Once a candidate is too large, every larger candidate is also too large.

Our target is the boundary between the two regions:

greatest true candidate

This differs from searching for a value in an existing sorted array. The array-search version asks whether a value appears or where a boundary lies among stored elements. Here, we manufacture the candidate values ourselves and use a calculation to decide whether each candidate is valid.

Build the Brute-Force Baseline

The direct approach follows the definition:

1. Start with candidate 0.
2. Test whether candidate * candidate <= x.
3. Keep going while the candidate is feasible.
4. Return the last feasible candidate.

A simple version is:

def my_sqrt_brute_force(x: int) -> int:
    answer = 0

    for candidate in range(x + 1):
        if candidate * candidate > x:
            break
        answer = candidate

    return answer

This is useful because it gives us a clear reference implementation for small test cases. If the binary-search version disagrees with this baseline on random small inputs, one of them is wrong.

But the baseline checks candidates one by one. Its work grows roughly with sqrt(x). The binary-search version can discard half of the remaining candidates after each test.

That is the leverage: we replace a long walk with repeated range elimination.

Choose Bounds and Search State

For a beginner-friendly implementation, use the inclusive search range:

low = 0
high = x

This is always safe:

• 0 is a valid candidate for every non-negative x.
• The square root cannot exceed x for this input domain.
• It also handles x = 0 without a special range setup.

We also maintain:

ans = 0

ans stores the greatest feasible candidate found so far.

Each variable has one job:

• low and high contain candidates that may still improve the answer.
• ans stores the best candidate already proven feasible.
• mid is the candidate we inspect next.

You can use a tighter upper bound for x >= 2:

high = x // 2

Every square root of an integer at least 2 is at most x // 2. But that optimization introduces extra reasoning for x = 0 and x = 1. The range [0, x] is clearer, and binary search already makes the difference irrelevant for this problem.

Maintain the Greatest-Feasible Invariant

The key invariant is:

ans is feasible, and every candidate that could produce a better answer is still inside [low, high].

At each iteration, calculate the midpoint:

mid = low + (high - low) // 2

Then test:

mid * mid <= x

There are two cases.

The midpoint is feasible

If:

mid * mid <= x

then mid can be the answer. Record it:

ans = mid

But there may be a larger feasible candidate, so search the right half:

low = mid + 1

The midpoint itself is already stored in ans, so it does not need to remain in the search interval.

The midpoint is infeasible

If:

mid * mid > x

then mid is too large. Because squares increase as the candidate increases, every value larger than mid is also infeasible.

Discard the midpoint and the entire right half:

high = mid - 1

The update directions follow directly from the predicate. Do not memorize them as arbitrary binary-search syntax:

• feasible means “the answer may be farther right”
• infeasible means “the answer must be to the left”

Invariant: Every value recorded in ans satisfies ans * ans <= x. Any candidate larger than ans that might still be feasible remains available for testing.

An exact square does not require a separate return branch. If x = 16 and mid = 4, the algorithm records 4, then searches right for a potentially larger feasible value. None exists, so the loop ends with ans = 4.

Returning immediately when mid * mid == x is also correct, but keeping one uniform branch makes the invariant easier to inspect.

Make the Arithmetic Safe

There are four implementation details worth checking before submitting.

Zero must be valid

For x = 0, the correct answer is 0.

Initializing:

low = 0
high = x
ans = 0

handles this naturally. The loop may not run, and ans is already correct.

For x = 1, the search tests candidates in [0, 1] and returns 1.

Compute the midpoint safely

Use:

mid = low + (high - low) // 2

This is the portable form of midpoint calculation. In languages with fixed-width integers, calculating (low + high) // 2 can overflow before the division occurs if both bounds are large.

Python integers do not overflow at the fixed-width boundary, but using the portable form keeps the implementation habit correct across languages.

Keep the feasibility test exact

In Python, mid * mid is an integer calculation. Keep it that way. Converting to floating point creates an unnecessary rounding problem and weakens the exact comparison the algorithm depends on.

The question is not “what approximate decimal value is the square root?” The question is exactly:

is this integer square at most x?

Account for fixed-width multiplication

The constraint fits in a 32-bit signed integer, but mid * mid can be larger than that range. In a fixed-width language, calculate the product in a wider integer type.

For example, in C++ you might cast mid to long long before multiplying.

Another overflow-aware option, when mid > 0, is to compare:

mid > x // mid

This is equivalent to:

mid * mid > x

without multiplying the two values. In Python, direct multiplication is safe and easier to read, so the implementation below uses it.

Trace a Non-Perfect Square

Let:

x = 8

Initial state:

low = 0
high = 8
ans = 0

low	high	mid	mid * mid	Decision	ans	Next interval
0	8	4	16	too large	0	[0, 3]
0	3	1	1	feasible	1	[2, 3]
2	3	2	4	feasible	2	[3, 3]
3	3	3	9	too large	2	[3, 2]

The interval is now empty because low > high. The answer is:

ans = 2

The final boundary is exactly what the problem asks for:

2 * 2 <= 8
3 * 3 > 8

The algorithm does not need to find an integer whose square equals x. It needs to find the last true result of the predicate.

Implement the Python Solution

Here is the complete integer square root Python implementation:

def my_sqrt(x: int) -> int:
    low = 0
    high = x
    ans = 0

    while low <= high:
        mid = low + (high - low) // 2

        if mid * mid <= x:
            # mid is feasible; try to find a larger feasible answer.
            ans = mid
            low = mid + 1
        else:
            # mid and every larger value are infeasible.
            high = mid - 1

    return ans

This uses no exponentiation operator, floating-point square root, or built-in square-root function.

Notice what the code does not contain:

• no special case required for x = 0
• no subtraction from a value after overshooting
• no floating-point approximation
• no ambiguous final pointer interpretation

The answer has its own variable, and every assignment to it is justified by the feasibility test.

Prove, Analyze, and Audit

Why the algorithm is correct

The predicate:

P(m): m * m <= x

is monotone over non-negative integers. If P(m) is false, then every larger candidate is also false because its square is larger. If P(m) is true, smaller non-negative candidates are also true.

Therefore:

• When a midpoint is feasible, discarding values below it cannot remove a better answer. We record the midpoint and search larger values.
• When a midpoint is infeasible, discarding it and every larger value cannot remove a feasible answer.
• Every value placed in ans is feasible.
• The search continues until no untested candidate can improve ans.

When the interval becomes empty, ans is feasible and no larger feasible candidate exists. Therefore ans is the greatest integer whose square is at most x.

Complexity

Each iteration removes roughly half of the remaining candidate range. Starting with at most x + 1 candidates gives:

• Time: O(log x) for positive x
• Space: O(1)

The algorithm uses only a fixed number of integer variables. No array, recursion stack, or auxiliary data structure grows with the input.

Edge-case audit

Before submitting, check:

Input type	Example	Expected result
Zero	0	0
One	1	1
Perfect square	4	2
Larger perfect square	16	4
Non-perfect square	8	2
Non-perfect square near a boundary	15	3
Maximum allowed input	2^31 - 1	46340

The maximum case also reminds you why multiplication deserves attention in fixed-width languages: the answer fits in a 32-bit signed integer, but squaring a candidate may require a wider intermediate type.

The transferable rule is simple:

When a discrete answer space has a feasibility predicate that changes once from true to false, binary-search the boundary. Decide whether you need the greatest feasible value or the first infeasible value, then make the bounds, midpoint, update direction, edge cases, and arithmetic safety explicit.

That is the reusable Sqrt(x) solution pattern: define the predicate, preserve the invariant, cut the search space, and return the boundary you proved.