Problem statement

Given a non-negative integer x, return the square root of x rounded down to the nearest integer.

Do not use any built-in exponent function or operator (sqrt, pow, **, …).

Example 1

Input: x = 4
Output: 2

Example 2

Input: x = 8
Output: 2
Explanation: √8 ≈ 2.828…, rounded down is 2.

Constraints

• 0 <= x <= 2147483647

Hints for Sqrt(x)

1. Hint 1

   Binary search the answer k on the condition k*k <= x.

2. Hint 2

   Watch for overflow in languages with fixed-size integers — compare k <= x / k instead.

How to solve Sqrt(x)

You are not searching an array — you are searching the answer space. The predicate k * k <= x is monotone: true for every k up to the root and false for every k above it. Binary searching for that boundary finds the floor of the square root without ever computing one.

Approach

1. Return x directly for x < 2, since sqrt(0) = 0 and sqrt(1) = 1.
2. Search k in [1, x], remembering the largest k that satisfies the predicate.
3. For each mid, test mid <= x / mid — an overflow-free way of asking mid * mid <= x.
4. If it holds, mid is feasible: record it and search higher. Otherwise search lower.
5. The last recorded feasible value is the floor of the root.

Why it works

For positive integers, mid * mid <= x and mid <= x / mid (with truncating division) are exactly equivalent: if mid * mid <= x then x / mid >= mid, and if mid * mid > x then x / mid <= mid - 1. So the rewritten test decides the same predicate while never forming a product that could overflow. Monotonicity then guarantees a single crossover point, which is what the search converges on.

Complexity

• Time — O(log x)
• Space — O(1)

Pitfalls

• mid * mid overflows 32-bit integers near the upper constraint of about 2.1 billion — compare with division instead.
• Handle x = 0 before the search, or the division test divides by zero.
• The answer is the floor, so keep the last feasible mid rather than returning where the loop stops.
• Built-in sqrt is disallowed, and on large inputs floating point rounds wrongly at exact squares anyway.

Reference solution

Python

def mySqrt(x: int) -> int:
    lo, hi = 0, x
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

Java

public static int mySqrt(int x) {
    if (x < 2) return x;
    int lo = 1, hi = x, best = 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid <= x / mid) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}

C++

int mySqrt(int x) {
    if (x < 2) return x;
    int lo = 1, hi = x, best = 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid <= x / mid) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}

JavaScript

var mySqrt = function(x) {
    let lo = 0, hi = x;
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (mid * mid <= x) lo = mid + 1;
        else hi = mid - 1;
    }
    return hi;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy