Problem: Given a number, num, find the square root of num and return it without using built-in functions to compute exponents. The answer should be rounded down to the nearest integer.

Constraints:

• 0 <= num < 2^31 - 1

Initial Thought Process (Brute-force)

At first, the question might appear to be hinting at using some esoteric mathematical method. However, that is most likely not the interviewer’s intention. Interview questions are more about allowing you to demonstrate your problem solving skills rather than a presupposed knowledge of arcane mathematical formulae.

Without a formula or built-in exponent functions, how would you find a square root of a number? A simple answer is to try all candidates. Do not worry if you don’t get to this point by yourself. A conversation with the interviewer will help in a real interview setting. Let us start with a brute-force solution of trying all possible candidates.

1
2
3
4
5
6
7

class Solution {
    public int sqrt(int num) {
        for (int candidate = 0; candidate < num; candidate++) {
            // Check whether the candidate is the answer.
        }
    }
}

While implementing the check for each candidate, one thing to keep in mind is that a square root of a number is not always an integer. In fact, the question requires that the answer should be rounded down to the nearest integer. With this in mind, our goal is to find the largest candidate such that candidate * candidate <= num. If candidate * candidate > num, then candidate is too big to be a square root for the given number.

Note that we are trying all integers from 0 with an increment of 1. Therefore, when find the first number candidate such that candidate * candidate > num, the answer must be the number that we tried immediately before, namely, candidate - 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int sqrt(int num) {
        // Keep track of the largest candidate that we tried
        // such that candidate * candidate <= num.
        int ans = 0;

        for (int candidate = 0; candidate < num; candidate++) {
            int diff = num - candidate * candidate;
            if (diff < 0) {
                break;
            }

            ans = candidate;
        }

        return ans;
    }
}

There is a bug in line 8 (highlighted) of our brute-force implementation. Since num can be as large as 2^31 - 1, multiplying it by itself can result in integer overflow. For example, if candidate is 100000, multiplying it by itself will not give the expected 10000000000 since we are using int data type. Specifically, in a signed 32-bit integer, the result will cause integer overflow and wrap around to 1410065408. We could either use double or use division rather than multiplication.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int sqrt(int num) {
        // Keep track of the largest candidate that we tried
        // such that candidate * candidate <= num.
        int ans = 0;

        for (int candidate = 0; candidate < num; candidate++) {
            if (num / candidate < candidate) {
                break;
            }

            ans = candidate;
        }

        return ans;
    }
}

Here, we simply check num / candidate < candidate which is equivalent to checking num < candidate * candidate. In general, it is important to check for edge cases during an interview, and integer overflow is a common edge case that you need to keep in mind while dealing with integers.

We can still make a small optimization in our brute-force approach. It is not required to check all numbers between 0 and num - 1. For instance, num was 1000, it would be unnecessary to check 900 for a square root candidate, because 900 cannot possibly be a square root. Without going into a mathematical proof, we can observe that a square root of a number is always at most half of the number. For example, sqrt(0) = 0, sqrt(4) = 2, sqrt(100) = 10, and so on. Therefore, let’s try candidates up to num / 2 rather than num.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int sqrt(int num) {
        // Keep track of the largest candidate that we tried
        // such that candidate * candidate <= num.
        int ans = 0;

        for (int candidate = 0; candidate <= num / 2; candidate++) {
            if (num / candidate < candidate) {
                break;
            }

            ans = candidate;
        }

        return ans;
    }
}

Complexity

Let N = num. The time complexity is O(N) because the solution iterates all numbers from 0 to N/2 and therefore takes a time proportional to N. The space complexity is O(1) because the solution requires a constant space.

Optimization (Binary Search)

When a brute-force solution linearly scans all possible answers, a common strategy to efficiently reduce the search space is to use a binary search. Since We know our search space is between 0 and num / 2, let’s start with the following. At first, do not worry too much about whether the boundary check is correct (e.g. lo <= hi). We can validate it later with some simple inputs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int sqrt(int num) {
        int lo = 1;
        int hi = num / 2;

        while (lo <= hi) {
            // Implement check
        }
    }
}

Let’s say that candidate is the middle of lo and hi. There are two cases for the binary search:

• If candidate * candidate > num, then, candidate is too big to be a square root of num. In that case, we should look consider the numbers less than candidate.
• If candidate * candidate <= num, then, candidate could be a rounded down square root of num. In that case, we should record candidate and consider all numbers greater than candidate.

These cases lead to the following implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int sqrt(int num) {
        int lo = 1;
        int hi = num / 2;
        int ans = 1;

        while (lo <= hi) {
            int candidate = (hi - lo) / 2 + lo;

            if (num / candidate < candidate) {
                hi = candidate - 1;
            } else {
                lo = candidate + 1;
                ans = candidate;
            }
        }

        return ans;
    }
}

Let’s run through the binary search with an input num of 9.

1. lo = 1,hi = 4, candidate = 2. Update lo = 2. Update ans = 2.
2. lo = 2,hi = 4, candidate = 3. Update lo = 3. Update ans = 3.
3. lo = 3,hi = 4, candidate = 3. Update lo = 4. Update ans = 3.
4. lo = 4,hi = 4, candidate = 4. Update hi = 3.
5. The binary search ends. Return ans = 3.

In addition, let’s test the solution against some possible edge cases. In an interview setting, this step of checking edge cases is especially important.

• If num = 0, we should return 0.
• If num = 1, we should return 1.

Our solution does not handle the case when num = 0. Let’s add a clause to handle that case.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int sqrt(int num) {
        if (num == 0) {
            return 0;
        }

        int lo = 1;
        int hi = num / 2;
        int ans = 1;

        while (lo <= hi) {
            int candidate = (hi - lo) / 2 + lo;

            if (num / candidate < candidate) {
                hi = candidate - 1;
            } else {
                lo = candidate + 1;
                ans = candidate;
            }
        }

        return ans;
    }
}

Validation

In addition, let’s add a validation to enforce the constraints. Here, we are doing it as a follow-up in order to focus the explanation on the algorithms. However, during an interview, it is a good idea to do this at the start.

1
2
3
4
5
6
7
8
9

class Solution {
    public int sqrt(int num) {
        if (num < 0) {
            throw new IllegalArgumentException("Input should not be negative.");
        }

        // ...
    }
}

We will not explicitly validate that num <= 2^31 - 1 because we are using an int data type whose largest value is 2^31 - 1. But you might want to implement that validation depending on the programming language of your choice.

Complexity

Let N = num. The time complexity is O(log(N)) because the search space is proportional to the input (~N/2), and the binary search cuts the search space by half on every step. The space complexity is constant.

Follow-ups

Round Up to the Nearest Integer

How will our binary search solution change if the requirement was to round up to the nearest integer, rather than rounding down?

To satisfy the requirement, we will need to keep track of the smallest value x such that x * x > num, rather than keeping track of the largest value x such that x * x <= num. To that end, we can simply move ans = candidate line from one branch to the other.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int sqrt(int num) {
        if (num < 0) {
            throw new IllegalArgumentException("Input should not be negative.");
        }
        if (num == 0) {
            return 0;
        }

        int lo = 1;
        int hi = num / 2;
        int ans = 1;

        while (lo <= hi) {
            int candidate = (hi - lo) / 2 + lo;

            if (num / candidate < candidate) {
                hi = candidate - 1;
                ans = candidate;
            } else {
                lo = candidate + 1;
                // ans = candidate;
            }
        }

        return ans;
    }
}

Find n-th Root

Now that we know how to find a square root, can we extend our binary search solution to find an n-th root?

One idea is to find an approximation of an n-th root by continually closing in on the better approximation with some margin of error.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    // A tolerated margin of error
    private double epsilon = 0.001;

    public double nthRoot(double num, int n) {
        double lo = 0;
        double hi = num;

        while (hi - lo > epsilon) {
            double candidate = (hi - lo) / 2 + lo;

            // Compute nth power of candidate using a loop because
            // the question forbids using built-in exponent functions.
            double pow = 1;
            for (int i = 0; i < n; i++) {
                pow = pow * candidate;
            }

            if (pow > num) {
                hi = candidate;
            } else {
                lo = candidate;
            }
        }

        return (hi - lo) / 2 + lo;
    }
}

Here, we use a binary search to get an approximate value within an accepted margin of error, by continually improving our guesses on every iteration.

Lessons Learned

1. If you need to find a value, sometimes the simplest thing is to try all candidates. Don’t assume that you need to know some mathematical formula.
2. Check for integer overflows when dealing with integers (especially when multiplying).
3. A binary search can be an optimization for a brute-force algorithm that does a linear scan.
4. If a search space is all integers, a binary search works naturally because the integers are sorted.
5. A binary search can be used to approximate a value, within a margin of error, by improving guesses over time.