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++