How to find the sqrt(num)

Problem statement

Compute and return the square root of a non-negative integer number.

The decimal digits are shortened, and only the integer component of the result is returned because the return type is an integer.

Example 1

  • Input: num = 8
  • Output: 2

Example 2

  • Input: num = 4
  • Output: 2

Solution

We can use binary search to solve this problem.

The intuition behind the solution is that the square root of the number lies in the range [2, num / 2]. So, we can consider the range to be an array of numbers and search for the integer part of the square root of the number.

The steps of the algorithm are as follows:

  1. Initialize start=2 and end=num/2.

  2. Until start <= end, do the following:

    1. Find the mid element using the formula start + (end - start) / 2.
    2. Find the square of the mid element, i.e., mid * mid and store it in a variable midSqr.
    3. If the midSqr is greater than num, it means the result lies in the left part of the array, i.e., from start to mid-1.
    4. If the midSqr is lesser than num, it means the result lies in the right part of the array, i.e., from mid+1 to end.
    5. If the midSqr is equal to num, it means we have found the result.
  3. When end > start, the loop finishes, and the end will be the result.

  • Time Complexity: O(log (num))
  • Space Complexity: O(1)

Look at the following illustration for a better understanding of the algorithm.

1 of 7

Code

import java.util.*;
public class Main{
private static int sqrt(int num){
int start = 2, end = num / 2;
while(start <= end){
int mid = start + (end - start) / 2;
long midSqr = (long) mid * mid;
if(midSqr > num) end = mid - 1;
else if(midSqr < num) start = mid + 1;
else return mid;
}
return end;
}
public static void main( String args[] ) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
System.out.printf("Sqrt(%s) = %s", num, sqrt(num));
}
}

Enter the input below

Free Resources