# 
#  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](https://www.educative.io/answers/what-is-a-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.
7. 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.

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

}

Java

How to find the sqrt(num)

Compute the integer square root of a non-negative number using binary search within the range [2, num/2].

How to find the sqrt(num)

Problem statement

Example 1

Example 2

Solution

Code