Square Root of Integer

Problem Statement: Given an integer A. Compute and return the square root of A. If A is not a perfect square, return floor(sqrt(A)). The value of A can cross the range of Integer.

Examples:

Example 1:

Input: 11

Output: 3

Explanation 1: When A = 11, the square root of A = 3.316. It is not a perfect square so we return the floor which is 3.

Example 2:

Input: 9

Output: 3

Explanation 2: When A = 9 which is a perfect square of 3, so we return 3.

Problem Constraints: 0 <= A <= 10¹⁰

Solutions:

Disclaimer: Don’t directly jump into the solution, first try it yourself.

Approach 1: Brute Force Approach

This approach is simple just iterate i from 1 to A and calculate (i*i) until we get i*i = A or ((i+1)*(i+1)) > A. Once we reach this condition just return i the value as output. The value i will be the Sqrt(A).

Code:

class Coderzpy {
 
    int sqrt(int A) {

        long ans = 0;
 
        for(long i = 0; i <= A; i++){
            
            if(i*i == A || (i+1)*(i+1) > A {
                ans = i;
            }
            
        }

        return (int) ans;
    }

    public static void main(String args[]) {
 
        int A = 11;
                    
        System.out.println("The sqrt is: "+
        sqrt(A));
   }
}

output: The sqrt is: 3

Time Complexity: O(sqrt(n)) for iterating each element until it reaches the i*i = sqrt(A);

Space Complexity: O(1).

Approach 2: Optimized Approach

In this approach, we are going to use Binary Search, to optimize the search time complexity by searching the elements within a confined search space.

Code:

class Coderzpy {
 
    public int sqrt(int A) {

        long left = 0;
        long right = A;

        while(left <= right) {

            long mid = (left + right) / 2;

            if(A == 2 || A == 1) {

                return 1;
            }

            if(mid*mid == A || (mid*mid < A &amp;&amp; (mid+1)*(mid+1) > A)) {

                return (int)mid;
            }

            if(mid*mid < A) {

                left = mid+1;
               
                
            }else {

                right = mid-1;
            }
        }

        return 0;
    }

    public static void main(String args[]) {
 
        int A = 11;
                    
        System.out.println("The sqrt is: "+
        sqrt(A));
   }
}

output: The sqrt is: 3

Time Complexity: O(log(n)) because using Binary Search to find the sqrt(A);

Space Complexity: O(1).