How to Find Square Root of a Number in Java? Example Solution

Write a program to calculate the square root of a number in Java or C++ is one of the popular coding interview questions from Programming job interviews both on tech companies like Facebook, Amazon, and investment banks like Citibank and Bank Of America, etc. The problem may look easy because you might know how to find the square root of a number but it's not. In fact, it's one of the tricky questions you would encounter in programming job interviews. The first hurdle is do you really remember how to calculate square root by hand? Many programmers don't. I know they have learned it past but when you ask them to calculate square root by hand, many won't remember the algorithm they have learned in school or college.

Some of them will answer that they will use the Math.sqrt() function to calculate the square root in Java,  as shown here, which is also right but the interviewer is not asking about that. he is asking you to develop your own method using algorithms to calculate the square root.

Some of the more intelligent programmers will then come up with something like they will use Newton's method to calculate the square root. Well, go on, if you remember how Newton's method works and you can explain that to the Interviewer, who might not have a good idea about it.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithms as possible to take advantage of all the knowledge available. You can also join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

So what leaves? Well, when this question was asked to me long back I had no clue about it. Like many others, I had also forgotten the algorithm to calculate square root by hand, but suddenly it strikes me that x = sqrt(y) and x^2 = y i.e. here X is the square root and you can possibly find the square root by computing square of x and checking it is less than or equal to Y. Once it is greater than Y, you can stop the loop. This looked possible to me and I started coding.

I wrote something like that

public static float root(int number) {
    float root = 0.0f;
    float square = root;
    while (square < number) {
      root++;
      square = root * root;
    }
    return root;
  }

Output
4
square root: 2.0
9
square root: 3.0
16
square root: 4.0
25
square root: 5.0
26
square root: 6.0

Even though it's not efficient and works only for a perfect square, I was happy to move forward on a problem I have not prepared. The Interviewer was then asked that for a non-perfect number square root is off by 1, how can you correct that? I said we can reduce the gap by using custom precision. 

Since we keep increasing the next possible square root by 1, we are getting an answer which is far from approximate, if we use 0.5 or 0.1, we'll get a more approximate answer as shown below.

public static float root(int number) {
    if (number < 0)
      return -1;
    if (number == 0 || number == 1)
      return number;
    float root = 0.0f;
    float precision = 0.1f;
    float square = root;
    while (square < number) {
      root = root + precision;
      square = root * root;
    }
    return root;
  }

Output
4
square root: 2.0000002
5
square root: 2.3
6
square root: 2.4999998
7
square root: 2.6999996
8
square root: 2.8999994
9
square root: 3.0999992

Though the answer was not perfect and the result was not very approximate, he gets the idea that by using lower precision we can make the square root more approximate and correct, but he was looking at something else as well. He asks me about the time complexity of the solution and I said it is linear because we are inching towards the right answer one step at a time.

Can we make it better? Well, I knew that logarithmic time is better than linear i.e. O(logN) is better than O(N), and when I think logN, the algorithm which comes to my mind was a binary search. Why not use a binary search to find the square root? That was another small step in the right direction and the following solution emerges from that:

public static float sqrt(int number) {
    if (number < 0)
      return -1;
    if (number == 0 || number == 1)
      return number;

    float start = 0.0f;
    float end = number;
    float precision = 0.001f;
    float middle = start;
    float difference = (float) Math.abs(Math.pow(middle, 2) - number);

    while (difference >= precision) {
      middle = (start + end) / 2.0f;

      if (Math.pow(middle, 2) > number) {
        end = middle;
      } else {
        start = middle;
      }

      difference = (float) Math.abs(Math.pow(middle, 2) - number);
    }
    return middle;
  }

Output
4
square root: 2.0
5
square root: 2.236023
6
square root: 2.449585
7
square root: 2.645935
8
square root: 2.8283691
9
square root: 3.0000916

Now, the algorithm is better in terms of runtime but it still has one critical problem which could lead to the program running forever, depending upon precision and the square root of a number. For example, if you change the precision to 0.00000001f and try to calculate the square root of 5, the program will go into an infinite loop because the condition difference >= precision will never become false.

Here, instead of greater than operator (>), we need to use the Float.compareTo() method to compare floating-point values. I have also explained that the right way to compare float values in Java is by using the Float.compareTo() method in my earlier article Why you shouldn't use == with float and double in Java?

This is one more reason why you should always use library methods for doing such primitive tasks as advised by Joshua Bloch in Effective Java. I leave it to you how you can avoid infinite loop while comparing float in Java here. It's a good topic to research and learn about.

Btw, this solution might help you to land a job in Java's application development role but not in a game programming domain or quant domain where they put a lot of emphasis on the fast and accurate algorithm. You might get some points here by coming up with a solution and improving it a bit which signifies that you have good learning ability, but video games are different bits.

They are quite math-intensive especially 3D games which do a lot of vector maths and put a lot of emphasis on performance even with modern hardware like NVIDIA graphics cards and fast CPU like intel i7. Don't you want your Minecraft and Quack fast and accurate?


As I said in the first paragraph, this problem might look easy but it is not and require a good understanding of floating-point arithmetic in the programming language you solve. You also need to know approximation algorithms like the Newton-Raphson algorithm which starts with a guess and refines it with iteration.

Here is a sample flowchart of calculating square root using the Newton-Raphson algorithm:

Other Algorithmic Interview Questions you may like to explore

• How to swap two numbers without using the third variable? (answer)
• Top 5 Courses to learn Data Structure and Algorithms (courses)
• How to check if two rectangles intersect with each other in Java? (solution)
• How to implement the sieve of the Eratosthenes algorithm in Java? (solution)
• How to add two numbers without using the plus operator in Java? (answer)
• How to implement a binary search tree in Java? (solution)
• How to implement pre-order traversal of a binary tree in Java? (solution)
• How to implement the binary search algorithm in Java? (solution)
• How to implement in-order traversal in Java? (solution)
• How to print all leaf nodes of a binary tree in Java? (solution)
• How to implement iterative quicksort in Java? (solution)
• Write a program to implement bubble sort in Java? (solution)
• How to implement the insertion sort algorithm in Java? (answer)
• 10 Free Data Structure and Algorithms Courses for Beginners (Courses)

Thanks for reading this article so far. If you find this data structure and algorithms interview question and tutorial useful then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.