Solving Algorithmic Problems: Square Root of an Integer

This post is part of a series on how to solve algorithmic problems. From my personal experience, I found that most of the resources were just detailing solutions. Yet, it was not very common to actually understand the underlying line of thought allowing to reach an efficient solution. Thereby, this is the goal of this series: describing potential processes of reflection to solve problems from scratch.


Problem

Implement sqrt(int a).
If a is not a perfect square, return floor(sqrt(a)).
Example:
Input: 4
Output: 2
Input: 11
Output: 3

Category: Binary search

Solving Process

Binary Search

The easiest solution would be to iterate from 1 to a and check the square value which results in a linear time complexity.

How to improve the complexity? Using a binary search with an O(log(n)) complexity. Bear in mind, every algorithm which removes half of the potential result during each iteration has an logarithmic complexity.

In pseudo-code:

int f(a) {
low = 1
high = a
  while low <= high {
mid = (high + low) / 2
current = mid * mid
    if current == a return mid
else if current < a
low = mid + 1
else if current > a
high = mid - 1
}
  return high // Because we need the floor value of sqrt
}

As you can see, the algorithm is pretty straightforward. Yet, there is one thing we must take care of as we are working with integer: making sure to not create an integer overflow.

An integer overflow occurs with an operation that results in a value outside of its own range. In Java, as an integer is encoded with 4 bytes, it goes from -2³¹ (-2147483648) to 2³¹-1 (2147483647).

Let’s imagine we would have implemented the previous algorithm using an int mid. In the case where a equals to Integer.MAX_VALUE, it will trigger an integer overflow during the first iteration resulting in having mid equals to -1073741824 (which is as you can imagine not what we expected).

Let’s implement a correct solution using long values:

In both return cases, it is safe to cast the long value into an int.

The algorithm complexity is O(log n) in time and O(1) in space (which by the way would not have been the case with a recursive implementation).


Further reading