Square Root of an Integer

Given a non-negative integer n, return its square root. If n is not a perfect square, return the floor of the square root: the largest x with x * x <= n. Do not use a built-in square root function.

LeetCode: 69. Sqrt(x)

Example

Input: 16   Output: 4
Input: 25   Output: 5
Input: 8    Output: 2     (2 * 2 = 4 <= 8, but 3 * 3 = 9 > 8)

Brute force: try every candidate

Count x up from 0 while (x + 1)² is still at most n. The square is computed as a long, because (x + 1)² can exceed Integer.MAX_VALUE.

public class Main {
    static int sqrt(int n) {
        long x = 0;
        while ((x + 1) * (x + 1) <= n) { // (x + 1)^2 is computed in long to avoid int overflow
            x++;
        }
        return (int) x;
    }

    public static void main(String[] args) {
        for (int n : new int[] {16, 25, 8, 0, 1, Integer.MAX_VALUE}) {
            System.out.println("sqrt(" + n + ") = " + sqrt(n));
        }
    }
}

sqrt(16) = 4
sqrt(25) = 5
sqrt(8) = 2
sqrt(0) = 0
sqrt(1) = 1
sqrt(2147483647) = 46340

Time: O(√n). Space: O(1).

Optimal: binary search on the answer

x * x <= n is true for every x up to the answer and false after it, so the answer can be found by binary search over 0 to n. Keep the invariant that lo always satisfies the condition and hi is the largest value that still might.

public class Main {
    static int sqrt(int n) {
        long lo = 0;
        long hi = Math.min(n, 46_340); // 46_340^2 is the largest square that fits in an int
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2; // round up, so lo = mid always makes progress
            if (mid * mid <= n) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return (int) lo;
    }

    public static void main(String[] args) {
        for (int n : new int[] {16, 25, 8, 0, 1, Integer.MAX_VALUE}) {
            System.out.println("sqrt(" + n + ") = " + sqrt(n));
        }
    }
}

sqrt(16) = 4
sqrt(25) = 5
sqrt(8) = 2
sqrt(0) = 0
sqrt(1) = 1
sqrt(2147483647) = 46340

Time: O(log n). Space: O(1).

Rounding mid up matters. With lo = 2, hi = 3 and rounding down, mid would be 2, lo = mid would not change anything, and the loop would never end.

Math.sqrt works on double, which the problem statement does not allow here.

Edge cases

• 0 and 1: their own square roots.
• Overflow: mid * mid overflows int for mid > 46340. Squaring in long avoids it, and so does comparing mid <= n / mid instead. The largest int input is Integer.MAX_VALUE (2147483647), whose floor square root is 46340.