Find Square Root of an Integer-Interview Problem

Difficulty: Medium

Asked in: Amazon, Microsoft, Facebook

Understanding the Problem: →

Given an integer, your task is to find the square root of the integer. For an integer x to be the square root of the given integer N, x*x must be equal to N.

For example: →

Input: 16
Output: 4

Explanation: 4x4 is equal to 16. Thus 4 is the square root of 16.

Similarly,

Input: 25
Output: 5

Possible follow-up questions to ask the interviewer: →

• An integer N can have x as well as -x as its square root. What should we output? ( Ans: Just output the positive square root)
• Do I need to handle for negative numbers?( Ans: No)

Solutions

We are going to see two different approach to solve this problem. The first one is a very simple while the second one is an efficient solution to come up with.

• Simple or Brute Force Solution: A simple iterative solution that iterates through all possible answers until we get the real answer.
• Efficient or Optimized Solution: This is an optimized solution where we are logically leaving out some of the elements and only checking for half of them. ( Guessed the Algorithm?)

Brute Force Solution

Solution idea

The idea here is to use simple iteration and to iterate through all the integers starting from 1 until we get the actual square root of the given integer. For each element i in the iteration, we will check if if i*i is equal to N(the given integer) or not. If not then i*i must be smaller than N. So, we will keep increasing i till we get the square root.

Solution steps

• We will initialize loop variable i with 1.
• We will check if i*i is equal to N. If that is the case, we got our square root. We will simply output i.
• Else i*i must be smaller than N, we will increment i.
• We will keep doing this, until we get our square root.

Pseudo-code

int getSquareRoot(int N)
{
   if(N==1 or N==0)
       return N   //Square root of 1 is 1 and of 0 is 0

  int i = 1
   int square = 1

  while(square is < or equal to N)
   {
      i+=1
      square = i*i

  }
   return i-1
}

Complexity Analysis

Time Complexity : O(N)

Space Complexity : O(1)

Critical ideas to think!

• Do we really need to check for all the elements iteratively? Can we reduce the time complexity?
• Are we handling the case when the given integer is not a perfect square?

Optimized Solution

Solution idea

The approach here is to stop checking for each and every possible element, instead we can ignore elements which are not going to yield the output based on an algorithm called as Binary Search. We will find a middle element by taking start as 1 and end as N. We will check the value of the square of the middle element. If the value is less than N, we will make start as middle element+1, else if the value is greater we will make end element as middle element-1. Also, we need to save the value of middle element in the first case as if the given integer is not a perfect square that can be a possible answer. In the case when the value is equal to N, we can output the value of middle element as it is the required square root.

Solution steps

• We will take two variable start =1 and end = N.
• We will find the middle element (mid) and apply binary search. The conditions are all same as a classic binary search algorithm.
• We just need another variable squareRoot to take care of the case when the given integer is not a perfect square. Then, we will output the floor of the square root.
• In case of perfect square, middle element( mid ) will be our answer and in the other case our answer is squareRoot.

Pseudo-code

int getSquareRoot(int N)
{
  if(N == 0 or N ==1)
     return N

 int start = 1
  int end = N

int squareRoot = 1
 
  while(start <= end)
  {
     int mid = (start+end)/2
     if((mid*mid) == N)
          return mid
     if((mid*mid) < N)
     {
          start = mid+1
          squareRoot = mid
     }

    else
          end = mid-1
   }
   return squareRoot
}

Complexity Analysis

Time Complexity : O(LogN)

Space Complexity: O(1)

Comparison of Different Solutions

Suggested Problems to Solve

• Find the prime factors of the given integer.
• Find the cube root of the given integer.
• Check if the given number is a perfect square or not. Try doing it without finding square root.
• Write a program to calculate Root Mean Square of a given integer.

Happy Coding! Enjoy Algorithms!!