Square Root of Integer InterviewBit Solution

Problem: Square Root of Integer


Problem Description:

Given an integer, A. Compute and return the square root of A.

If A is not a perfect square, return floor(sqrt(A)).


DO NOT USE SQRT FUNCTION FROM STANDARD LIBRARY.


Input Format

The first and only argument given is integer A. 

Output Format

Return floor(sqrt(A)) 

Constraints

1 <= A <= 10^9 

For Example

Input 1:
    A = 11
Output 1:
    3
Input 2:
    A = 9
Output 2:
    3


Approach


To find sqrt of a number, we can do binary search on range, 0 to the given number. If for any mid-value, it's square increases more than the given number we will shift towards the lower number, otherwise the higher number.



Time & Space Complexity:

Time Complexity: O(logN)
Space Complexity: O(1)


Solution:


Code in C++