(**Asked in AMAZON, ACCOLITE, FLIPKART, VMWare..etc**)

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

**Input:**

First line of input contains number of testcases T. For each testcase, the only line contains the number x.

**Output:**

For each testcase, print square root of given integer.

**Your Task:**

The task is to complete the function **floorSqrt**() which should return the square root of given number x.**Expected Time Complexity:** O(log N).**Expected Auxiliary Space:** O(1).

**Constraints:**

1 ≤ T ≤ 10000

1 ≤ x ≤ 10^{7}

**Example:****Input**:

2

5

4**Output**:

2

2

**Explanation:Testcase 1: **Since, 5 is not perfect square, so floor of square_root of 5 is 2.

**Testcase 2:**Since, 4 is a perfect square, so its square root is 2.

**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**.

**Note: I suggest you don’t use any library function to find square root because of time complexity the given solution in** **O(LogN)**.

**Code:**

```
package searchingSorting;
import java.util.Scanner;
public class SquareRoot {
static long root(long x) {
long start = 0;
long end = x;
while(start <= end) {
long mid = (start + end) / 2;
if((mid * mid) == x)
return mid;
if((mid * mid) < x)
start = mid + 1;
else
end = mid - 1;
}
return (long) Math.floor(end);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long x = sc.nextLong();
System.out.println(root(x));
}
}
```

Hope you guys understand the above code..

**Thanks for reading…!**

**Thank You..!**

**Happy Coding…!**