Square root of an integer

link 0

Given an integer x, find square root of it. If x is not a perfect square, then return floor(√x).

Examples:

Input: x = 4
Output: 2

Input: x = 11
Output: 3

There can be many ways to solve this problem. For example Babylonian Method is one way.

Simple Solution to find floor of square root is to try all numbers starting from 1. For every tried number i, if i*i is smaller than x, then increment i. We stop when i*i becomes more than or equal to x. Below is C++ implementation of above idea.

/ A C++ program to find floor(sqrt(x)
#include<bits/stdc++.h>
using namespace std;
// Returns floor of square root of x
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
       return x;
    // Staring from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result < x)
    {
       if (result == x)
          return result;
       i++;
       result = i*i;
    }
    return i-1;
}
// Driver program
int main()
{
    int x = 11;
    cout << floorSqrt(x) << endl;
    return 0;
}

Output:

3

Time complexity of the above solution is O(√ n). Thanks Fattepur Mahesh for suggesting this solution.

Better Solution to do Binary Search.

Let  's' be the answer.  We know that 0 <=  s <= x.

Consider any random number r. 

    If r*r <= x, s >= r

    If r*r > x, s < r. 

Algorithm:
1) Start with ‘start’ = 0, end = ‘x’,
2) Do following while ‘start’ is smaller than or equal to ‘end’.
a) Compute ‘mid’ as (start + end)/2
b) compare mid*mid with x.
c) If x is equal to mid*mid, return mid.
d) If x is greater, do binary search between mid+1 and end. In this case, we also update ans (Note that we need floor).
e) If x is smaller, do binary search between start and mid-1

Below is C++ implementation of above idea.

// A C++ program to find floor(sqrt(x)
#include<bits/stdc++.h>
using namespace std;
// Returns floor of square root of x        
int floorSqrt(int x)
{   
    // Base cases
    if (x == 0 || x == 1)
       return x;
    // Do Binary Search for floor(sqrt(x))
    int start = 1, end = x, ans;  
    while (start <= end)
    {       
        int mid = (start + end) / 2;
        // If x is a perfect square
        if (mid*mid == x)
            return mid;
        // Since we need floor, we update answer when mid*mid is
        // smaller than x, and move closer to sqrt(x)
        if (mid*mid < x)
        {
            start = mid + 1;
            ans = mid;
        }
        else // If mid*mid is greater than x
            end = mid - 1;       
    }
    return ans;
}
 
// Driver program
int main()
{    
    int x = 11;
    cout << floorSqrt(x) << endl;
    return 0;  
}

Output:

3

Time Complexity: O(Log x)

Note: The Binary Search can be further optimized to start with ‘start’ = 0 and ‘end’ = x/2. Floor of square root of x cannot be more than x/2 when x > 1.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/shuffle-2n-integers-format-a1-b1-a2-b2-a3-b3-bn-without-using-extra-space/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar