How to find Square root of integer in Java without using any Library? Interview Question

Problem : Given an integer i, find square root of it, without using Math.sqrt() method. Your method should return square root if given number is perfect square otherwise return floor(sqrt(x));

For example, 

Input i = 16

Output : 4

Input i = 17

Output : 4

This is very interesting problem and asked both freshers and experienced programmers. I have seen this question on many companies including ANZ, Barclays, and Citibank.

 

Since JDK provides a powerful Math API, many programmer answer the question by suggesting Math.sqrt() method, but if you ask them to code a solution by themselves, they struggle. 

Btw, there are many ways to solve this problem e.g. you can use Babylonian method, but in this article, we will explore a simple and interesting solution using binary search.

Since square root of a number is always greater than or equal to zero but less than the number, you can deduce that for a any random integer i

if i*i <= number then square root >= i

if i*i > number than square root < i

Solution

Here is the algorithm (steps) to solve this problem in Java :

1) Start with start = 0 and end = number

2) Until start is less tha nor equal to end :

a) calculate mid = (start + end)/2

b) compare mid*mid with number

c) if number is equal to mid*mid, return mid (number is perfect square and mid is square root)

d) if number is greater than mid*mid, do binary search between mid + 1 and end. In this case answer will be floor of square root

e) if xnumber is less than mid*mid, do binary search between start and mid -1

Java Program to Calculate Square Root 

Here is our Java program based upon these steps :

/**

* Returns square root of a number if its perfect square

* otherwise, return floor of square root 

* @param number

* @return

*/

public static int sqrt(int number) { 

// Base cases

if (number == 0 || number == 1) 

return number;

// Do Binary Search for floor(sqrt(x))

int start = 1, end = number, ans = 0; 

while (start <= end) 

{ 

int mid = (start + end) / 2;

// If number is a perfect square

if (mid*mid == number)

return mid;

// Since we need floor, we update answer when mid*mid is 

// smaller than number, and move closer to sqrt(x)

if (mid*mid < number) 

{

start = mid + 1;

ans = mid;

} 

else // If mid*mid is greater than x

end = mid - 1; 

}

return ans;

}

Since this solution is based upon binary search, time complexity of solution is O(logN) . The binary search can be optimized further by checking from 0 until X/2, as the square root of a number cannot be higher than number/2.

That's all about how to calculate square root of an integer in Java without using any library method. If you know any other solution of this interview problem then feel free to suggest in comments.