## Square root of a number in java

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

Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)

Note: Try Solving the question without using sqrt Function.

### Input Format

• The only line contains an integer x.

### Output Format

Print the square root of x.

### Example 1

Sample Input

```5
```

Sample Output

```2
```

Explanation

```Since, 5 is not a perfect square, floor of
square_root of 5 is 2.
```

• 1 ≤ x ≤ 10^7

## Solution:–

```import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
public static void main (String[] args) throws java.lang.Exception
{
// ans will lie between 1 and n
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long l = 1, r = n;
long mid, ans = 1;
while(l <= r){
mid = (l + r) / 2;
if(mid * mid > n)
r = mid - 1;
else if(mid * mid < n){
l = mid + 1;
// But, this could be our ans also
// If (mid + 1) * (mid + 1) > n
// It means -> mid < sqrt(n) < mid + 1
// It means mid is the integer part and hence our ans
if((mid + 1) * (mid + 1) > n){
// n lies between Square of mid and mid + 1
ans = mid;
break;
}
}
else{ // mid * mid == n
ans = mid;
break;
}
}
System.out.println(ans);
}
}```