Square root of an integer

The problem, simply

You get a whole number x that is 0 or more. Return its square root rounded down: the biggest whole number r with r * r <= x. You may not use Math.sqrt or a power function.

For example the square root of 8 is about 2.83, so the answer is 2.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try sides 1, 2, 3, ... while the square still fits. The last side that fits is the answer.

class Solution {
    public int mySqrt(int x) {
        long r = 0;
        while ((r + 1) * (r + 1) <= x) r++;   // the next side still fits
        return (int) r;
    }
}

How long it takes: about sqrt(x) steps, O(sqrt(x)). For the biggest int that is 46340 steps, which is fine once, but slow if asked millions of times. Extra room: O(1).

Way 2: the clever way

Binary search the side.

1. If x < 2, return x.
2. The answer is between 1 and x / 2, because for x >= 4 the square root is at most half of x (and for 2 and 3 the answer is 1).
3. Take mid. If mid * mid <= x, it fits: remember it and look for a bigger side (lo = mid + 1). Otherwise it is too big (hi = mid - 1).
4. The last side that fit is the answer.

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        long lo = 1, hi = x / 2, answer = 1;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid * mid <= x) {        // long math, so no overflow
                answer = mid;            // fits: try a bigger side
                lo = mid + 1;
            } else {
                hi = mid - 1;            // too many tiles: smaller side
            }
        }
        return (int) answer;
    }
}

How long it takes: the range halves each round, O(log x), about 31 rounds at most. Extra room: O(1).

Another way: Newton's method

Start with a guess r = x. Replace it by the average of r and x / r while r * r > x. If r is too big, x / r is too small, and their average is closer. The number of correct digits roughly doubles each round.

class Solution {
    public int mySqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
}

This is also O(log x) in the worst case, and much faster once it gets close. It is what calculators and libraries do, in spirit.

Watch out for

• Returning lo or hi at the end without thinking. With this loop, hi ends as the answer too, but keeping answer is clearer.
• hi = x / 2 is wrong for x = 1 (it gives 0). That is why x < 2 is handled first.
• Using Math.sqrt and casting is often allowed in real code, but floating point can be off by one for huge long values. Fix with a small while check.

What interviewers ask next

• Return the square root with 6 digits after the point. Binary search on doubles for about 60 rounds, or use Newton's method.
• Is x a perfect square? Find the floor square root and check r * r == x.
• The cube root, or the k-th root. Same search, with mid^k <= x, careful with overflow.
• Why not search [0, x]? You can. It costs one extra round. x / 2 is just a tighter start.

Remember this

Grown-up words: the side length is the integer square root (floor of the square root), "higher or lower" is binary search on the answer, and averaging r with x / r is Newton's method.