Square Root (Integer)

Q: What is the time complexity of the binary search square root?

O(log x) time and O(1) space: each step halves the range, so x = 2^31 - 1 needs 31 steps. Counting up from 0 takes O(√x) steps, 46340 for the same x .

Q: How does Newton's method compute an integer square root?

Start with r = x . While r × r > x , replace r with (r + x / r) / 2 using integer division. Each step moves r down toward the root without passing it, and the loop stops at the floor of the square root. For x = 2^31 - 1 it needs 19 steps.

EasyBinary search Math and simulation

+10

Your function gets a non-negative integer x and returns its integer square root: the largest integer r with r × r ≤ x. That is the square root rounded down, so a number that is not a perfect square gets the root of the perfect square below it. Compute it yourself, without a built-in square root or power function.

Function

mySqrt(x: integer) → integer

xinteger: the non-negative integer to take the square root of
Returnsinteger: the square root of x rounded down to an integer

Constraints

0 ≤ x ≤ 2³¹ - 1
Do not call a built-in square root, power or exponent function.

Examples

Input: x = 17
Output: 4
Explanation: 4 × 4 = 16 is at most 17, but 5 × 5 = 25 is more, so the root of 17 rounds down to 4.

Input: x = 49
Output: 7
Explanation: 49 is a perfect square, 7 × 7 = 49, so nothing is rounded and the answer is exactly 7.

Follow-up

How would you find the integer cube root instead, the largest r with r × r × r ≤ x, if x could also be negative?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The squares 0, 1, 4, 9, 16 and so on are sorted, so you can binary search for the last number whose square is at most x in about 31 steps. The trap is overflow: a candidate's square does not always fit in 32 bits.

Count up from zero

Intuition

Start at r = 0 and step to r + 1 while the square of the next number is still at most x. The loop stops at the first r whose successor is too big, which is the root. For x = 17 the squares 1, 4, 9 and 16 fit and 25 does not, so the loop stops at 4.

The largest root here is 46340, so the loop runs at most 46340 times. The cost grows with the input, though: a 64-bit x could take about 3 × 10^9 steps.

Algorithm

Set root = 0.
While (root + 1) × (root + 1) ≤ x (in 64 bits), increase root by 1.
Return root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Binary search on the answer

Intuition

Ask each candidate from 0 to x whether its square is at most x. Squares only grow, so the answers read yes up to the root and no after it. The root is the last yes, which binary search finds by halving the range of undecided candidates. Keep the largest yes seen so far in best.

For x = 17 the search tests 8 (64, too big), 3 (9, fits), 5 (25, too big) and 4 (16, fits). The range is then empty and best is 4. For x = 2^31 - 1 it takes 31 steps.

Algorithm

Set lo = 0, hi = x and best = 0.
While lo ≤ hi, take mid = lo + (hi - lo) / 2.
If mid × mid ≤ x (in 64 bits), set best = mid and lo = mid + 1.
Otherwise set hi = mid - 1.
Return best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Pitfalls and edge cases

Squaring in 32 bits. For x = 2147483647 the first mid is 1073741823, whose square is about 1.15 × 10^18 and wraps to a wrong value. Multiply in 64 bits, or compare m ≤ x / m.
The same overflow in the counting loop: its last check squares 46341, which gives 2147488281, above the 32-bit limit.
Using an exclusive bound hi = x + 1. For the largest x that is 2147483648, one past the 32-bit limit.
Returning the last mid tested. For x = 17 the search ends after testing 5; the answer is the remembered 4.
Starting the search at lo = 1, which misses x = 0. The check m ≤ x / m also divides by zero when m = 0.

Frequently asked questions3

What is the time complexity of the binary search square root?

O(log x) time and O(1) space: each step halves the range, so x = 2^31 - 1 needs 31 steps. Counting up from 0 takes O(√x) steps, 46340 for the same x.

How does Newton's method compute an integer square root?

Start with r = x. While r × r > x, replace r with (r + x / r) / 2 using integer division. Each step moves r down toward the root without passing it, and the loop stops at the floor of the square root. For x = 2^31 - 1 it needs 19 steps.

Why does the solution need 64-bit integers when the answer fits in 32 bits?

The answer is at most 46340, but the candidates you test are not. Binary search over 0 to x first tries a candidate near 10^9, whose square is near 10^18, far beyond the 32-bit limit of about 2.1 × 10^9.