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.

### Constraints

- 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); } }

## Add a Comment