Topics › Binary Search › BS on Answers

Find square root of a number

Medium TUF ID 92 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a non-negative integer n. Return the integer square root of n, that is the largest integer r such that r * r ≤ n. In other words, return floor(sqrt(n)). You must not rely on the floating-point result being exact; the answer has to be correct for every n in range.

Constraints: 0 ≤ n ≤ 2^31 - 1 (a 32-bit signed integer).

Example 1

n = 28
answer = 5          // 5 * 5 = 25 <= 28, but 6 * 6 = 36 > 28

Example 2

n = 36
answer = 6          // perfect square, 6 * 6 = 36 exactly

This is the first problem in the “binary search on answers” family. Nothing here is an array; instead the set of candidate answers 0, 1, 2, ..., n is the sorted sequence we search, and the condition r * r ≤ n plays the role of “is this element small enough”.

Approach 1: Brute force, count upwards

Intuition. Try i = 1, 2, 3, ... and stop at the first i whose square exceeds n. The answer is the previous i. Because squares increase with i, once i * i > n no larger i can work, so stopping early is safe.

Algorithm.

1. Set ans = 0.
2. For i = 1, 2, 3, ... while i * i ≤ n: set ans = i.
3. Return ans.

static int bruteForce(int n) {
    int ans = 0;
    for (long i = 1; i * i <= n; i++) ans = (int) i;
    return ans;
}

Complexity. Time O(sqrt n): the loop runs floor(sqrt n) times, at most about 46341 iterations for a 32-bit n. Space O(1).

The loop variable is a long on purpose. When i reaches 46341, i * i is 2,147,488,281, which is larger than Integer.MAX_VALUE; with an int loop variable the product would wrap to a negative number, the condition i * i <= n would stay true, and the loop would keep going and return garbage. Keeping i a long makes the multiplication a long multiplication.

For a single query of a 32-bit number this is fast enough. The point of the problem, though, is to practise the O(log n) technique that scales to 64-bit inputs and to the harder problems that follow.

Approach 2: Optimal, binary search on the answer

Intuition. Look at the predicate P(r) = (r * r ≤ n) over r = 1, 2, 3, .... It is monotonic: true for all small r, then false forever after some point. The sequence looks like T T T T F F F F ..., and the answer is the position of the last T. Whenever a predicate has this shape we can binary search it: test the middle candidate; if it is true, the last T is at mid or to the right, so record mid and search right; if it is false, search left.

Algorithm.

1. Set lo = 1, hi = n, ans = 0 (if nothing in [1, n] works, the answer is 0, which only happens for n = 0).
2. While lo ≤ hi:
   • mid = lo + (hi - lo) / 2.
   • If mid * mid ≤ n (computed in long): ans = mid, lo = mid + 1.
   • Else: hi = mid - 1.
3. Return ans.

static int optimal(int n) {
    int lo = 1, hi = n, ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if ((long) mid * mid <= n) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return ans;
}

Dry run on n = 28:

Result 5. Observe that when the loop ends, hi also equals the answer: the final hi is always the last index where the predicate was true. Returning hi instead of tracking ans is a common shortcut, but the explicit ans variable is easier to reason about and generalises to every other problem in this family.

Complexity. Time O(log n): the range [1, n] is halved each step, about 31 iterations for a 32-bit n. Space O(1).

Two details matter:

• (long) mid * mid casts mid to long before multiplying. Writing (long) (mid * mid) would multiply two ints first, overflow, and then widen the wrong value. For n = Integer.MAX_VALUE the search visits mid values above 46341, whose squares do not fit in an int.
• mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2 avoids overflow of the sum when hi is near Integer.MAX_VALUE.

A tighter upper bound such as hi = min(n, 46341) or hi = n / 2 + 1 shaves a few iterations but changes nothing asymptotically.

Approach 3: Library square root with a fix-up

Intuition. Math.sqrt computes the floating-point root in constant time, and for every 32-bit n the double result is accurate enough that truncating it gives the correct answer or something off by one. Rather than trusting that, apply the exact integer check and nudge the candidate down while it is too big and up while the next integer still fits. The two while loops rarely execute even once, but they make the method provably correct regardless of rounding.

Algorithm.

1. r = (int) Math.sqrt(n).
2. While r * r > n: r--.
3. While (r + 1) * (r + 1) ≤ n: r++.
4. Return r.

static int builtin(int n) {
    int r = (int) Math.sqrt(n);
    while ((long) r * r > n) r--;
    while ((long) (r + 1) * (r + 1) <= n) r++;
    return r;
}

Complexity. Time O(1) in practice (the fix-up loops run a constant number of times). Space O(1).

In an interview, mention this as the pragmatic production answer, then show the binary search, because the binary search is what transfers to problems where no library function exists.

Edge cases and pitfalls

• n = 0 and n = 1. The answers are 0 and 1. In the binary search hi = 0 makes the loop body never run and ans stays 0; for n = 1 the single candidate 1 passes.
• Perfect squares. 36 must return 6, not 5. The predicate uses ≤, not <; with < every perfect square would be off by one.
• Overflow in mid * mid. Covered above; the Java test with Integer.MAX_VALUE exercises it. The expected answer is 46340 because 46340^2 = 2,147,395,600 ≤ 2^31 - 1 and 46341^2 is not.
• Boundary squares. 2,147,395,599 returns 46339, while 2,147,395,600 returns 46340. These two inputs sit on either side of a perfect square and catch off-by-one mistakes in the predicate.
• Floating-point trust. (int) Math.sqrt(n) alone is correct for 32-bit inputs but can be wrong for large long inputs where double loses precision. The fix-up loops in Approach 3 cost nothing and remove the doubt.
• Negative input. The square root of a negative number is undefined for integers; the problem guarantees n ≥ 0. If you must be defensive, return -1 or throw before the search.

Related problems

• Find Nth root of a number is the same search with mid^n instead of mid^2 and a stricter “exact root or -1” requirement.
• Koko eating bananas replaces the arithmetic predicate with one computed from an array, which is the general shape of “binary search on answers”.
• Find the smallest divisor and Capacity to Ship Packages Within D Days use exactly the same lo / hi / ans skeleton.