Calculate the Square Root of an Integer

Problem

• Square root of an integer: InterviewBit

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

• Solving Algo publication

Follow me on Twitter @teivah