Square root of a number

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