Sqrt(x)

NeetCode: Sqrt(x) · LeetCode: 69. Sqrt(x) · Difficulty: Easy

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. Do not use a built-in exponent or square-root function.

Example

Text

Input:  x = 4    Output: 2
Input:  x = 8    Output: 2    (sqrt(8) = 2.828..., rounded down)
Input:  x = 0    Output: 0

The answer is the largest r with r * r <= x. All arithmetic is in integers, which avoids floating-point rounding. With x up to Integer.MAX_VALUE, a candidate r near 46341 gives r * r slightly above 2^31. An int product wraps to a negative number there, so the products are computed in long.

Brute force: count up until the square is too big

Increase r while (r + 1)^2 <= x. It stops after about sqrt(x) steps.

Java

class Solution {
    public int mySqrt(int x) {
        long r = 0;
        while ((r + 1) * (r + 1) <= x) {
            r++;
        }
        return (int) r;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mySqrt(4));
        System.out.println(s.mySqrt(8));
        System.out.println(s.mySqrt(0));
        System.out.println(s.mySqrt(1));
        System.out.println(s.mySqrt(2147395599));
    }
}

Output

Time: O(sqrt(x)). Space: O(1).

Optimal: binary search on the answer

The predicate r * r <= x is true for small r and false for large r, so it is monotonic and the last true can be found by binary search. Search the half-open range [lo, hi) up to x + 1 for the first r whose square exceeds x; the answer is one less. The variables are long, so x + 1 does not overflow when x is Integer.MAX_VALUE, and mid * mid stays far below 2^63.

Java

class Solution {
    public int mySqrt(int x) {
        // Find the first r in [0, x + 1] with r * r > x; that is at least 1.
        long lo = 0;
        long hi = (long) x + 1;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid * mid > x) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return (int) (lo - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mySqrt(4));
        System.out.println(s.mySqrt(8));
        System.out.println(s.mySqrt(0));
        System.out.println(s.mySqrt(1));
        System.out.println(s.mySqrt(2147395599));
        System.out.println(s.mySqrt(Integer.MAX_VALUE));
    }
}

Output

Why lo - 1 is never negative: r = 0 has 0 * 0 = 0, which is never > x, so the first r with square above x is always at least 1. Newton's method also works and converges faster.

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