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