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 of candidates, so x = 2^31 - 1 needs 31 steps. Counting up from 0 takes O(√x) steps, 46340 for the same x , which is fine here but grows quickly with 64-bit inputs.

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, and the number of correct digits roughly doubles per step once it gets close.

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.

+17 hidden tests on Submit

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

Counting up from 0 until the next square passes x gives the right answer, but it takes one step per unit of the root, about 46000 steps near the top of the range. The squares 0, 1, 4, 9, 16 and so on are sorted, so you can binary search for the last candidate whose square is at most x and finish in about 31 steps. The trap in both is overflow: a candidate's square does not always fit in 32 bits.

Count up from zero

Intuition

The root is the largest r with r × r ≤ x. Start at r = 0, whose square always fits, and keep stepping to r + 1 while the square of the next number still fits. The loop stops at the first r whose successor is too big, which is exactly the root. For x = 17 the squares 1, 4, 9 and 16 fit and 25 does not, so the loop stops at 4.

The loop runs once per unit of the answer. The largest answer here is 46340, so at most 46340 steps, which finishes fast. The cost is O(√x), though, and it grows with the input: a 64-bit x could take about 3 × 10^9 steps.

Watch the last check. For x = 2^31 - 1 the loop squares 46341 to learn that it is too big, and 46341 × 46341 = 2147488281 does not fit in a 32-bit integer. Square in 64 bits.

Algorithm

Set root = 0.
While (root + 1) × (root + 1) ≤ x, 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

Line up the candidates 0, 1, 2, up to x, and ask each one the same question: is its square at most x? The answers come out yes, yes, yes, then no for every candidate after the root, because squares only grow. The root is the last yes. A sorted run of yes followed by no is what binary search is built for.

Keep the range lo to hi of candidates not yet decided, starting at 0 to x, and a variable best for the largest yes so far. Test the middle mid. If mid × mid ≤ x, the root is mid or larger: store it in best and move lo to mid + 1. Otherwise the root is smaller: move hi to mid - 1. When the range is empty, best is the root.

Trace x = 17. The range 0 to 17 tests 8 (64, too big), then 0 to 7 tests 3 (9, fits, best = 3), then 4 to 7 tests 5 (25, too big), then 4 to 4 tests 4 (16, fits, best = 4). The range is empty and the answer is 4. Each step halves the range, so x = 2^31 - 1 takes 31 steps. Do the squaring in 64 bits: the first mid there is 1073741823.

Algorithm

Set lo = 0, hi = x and best = 0.
While lo ≤ hi, compute mid, the middle of the range.
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

The search itself is short; the bugs hide in the arithmetic and the edges.

Squaring in 32 bits. For x = 2147483647 the first middle candidate is 1073741823, and its square is about 1.15 × 10^18. In a 32-bit int that wraps around to a wrong value, which can even look small enough to fit. Do the multiplication in 64 bits, or compare m ≤ x / m instead.
Squaring the next candidate in 32 bits in the counting loop. The root of 2^31 - 1 is 46340, and the loop's last check squares 46341, which gives 2147488281, above the 32-bit limit.
Pushing the range past 32 bits. An exclusive bound hi = x + 1 is 2147483648 for the largest x, one past the 32-bit limit. With the inclusive hi = x, lo + hi peaks at exactly 2147483647 on the first step, so it fits with no room to spare. Use 64-bit indexes or lo + (hi - lo) / 2.
Returning the last mid you looked at instead of the last one that fit. For x = 17 the search ends after testing 5, which is too big; the answer is the remembered 4.
Breaking the small cases. A search that starts at lo = 1 misses x = 0, and the division check m ≤ x / m divides by zero when m = 0. Test 0 and 1 on their own.

Frequently asked questions4

How do you find a square root without a built-in function?

For an integer square root, binary search the answer. The candidates 0 to x split into a run whose squares are at most x and a run whose squares are larger, and binary search finds the last candidate of the first run. Newton's method is the other common answer: it refines a guess r with (r + x / r) / 2 until the square fits.

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

O(log x) time and O(1) space. Each step halves the range of candidates, so x = 2^31 - 1 needs 31 steps. Counting up from 0 takes O(√x) steps, 46340 for the same x, which is fine here but grows quickly with 64-bit inputs.

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, and the number of correct digits roughly doubles per step once it gets close.

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, and its square is near 10^18, far beyond the 32-bit limit of about 2.1 × 10^9. Squaring in 64 bits keeps the comparison exact. Comparing m ≤ x / m avoids the large product altogether.