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

- The only line contains an integer x.

#### Constraints

- 1 ≤ x ≤ 10^7

#### Output

Print the square root of x.

#### Example

**Sample Input**

5

**Sample Output**

2

**Explanation**

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

## Solution:–

import java.util.*; import java.lang.*; import java.io.*; public class Main { static int floorSqrt(int x) { // Base cases if (x == 0 || x == 1) return x; // Starting from 1, try all numbers until // i*i is greater than or equal to x. int i = 1, result = 1; while (result <= x) { i++; result = i * i; } return i - 1; } public static void main (String[] args) throws java.lang.Exception { //your code here Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.print(floorSqrt(n)); } }

## Add a Comment