Friday, 20 July 2018

C++ Program to find the square root of Number in log(n)

The idea is simple. We will use binary search to find the square root of the number. If the given number is not a perfect square then we will simply take the floor value of the root of the number.. Algorithm to find the square root of a number in log time is given below along with its implementation in C++.

For example: if  n = 10 then answer is 3 and if n==25 then answer is 5

Algorithm:

1. set start=1
2. set end=n
3. do while (start<=end):
4.           set mid=(start+end)/2
5.           if  (mid*mid=n) return mid
6.           else if (mid*mid<n)
7.                  set ans=mid
8.                  set start=mid+1
9.           else
10.                set end=mid-1
11. return ans



PROGRAM:

#include <bits/stdc++.h>
using namespace std;

int findFloorRoot(int n){
  
  int start=1,end=n;
  int ans;
  while(start<=end){

     //calculate middle value
          int mid=(start+end)/2;

          //if nis a perfect square of mid then return mid
          if(mid*mid==n) return mid;

          else if(mid*mid<n){
              ans=mid;  //if n is not a perfect square then take the floor value
              start=mid+1;
          }
          else 
              end=mid-1;
  }
  return ans;
}

int main(){
  
  int n;
  cout<<"\nEnter the number: ";
  cin>>n;
  int ans=findFloorRoot(n);
     cout<<"\nThe root of the n is: \n\n";
     cout<<ans;
     cout<<"\n";
     return 0;
}

OUTPUT:




EmoticonEmoticon