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

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 Complexity: O(logN)

Space Complexity: O(1)

Code in C++