Square root of a number in java

Square root of a number in java

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

Your email address will not be published. Required fields are marked *