Problem Statement

1Problem Description : Given a non negative integer n, find the largest integer that is less than or equal to √n. It means 
2if n is not a perfect square return floor(√n).
3
4NOTE : Do not use sqrt function from standard library.
5
6Constraints: 0 <= n <= 231 - 1
7
8Input: An integer n
9
10Output: floor(√n)

1Example1 :
2
3  Input : 9
4
5  Output: 3
6
7  Explanation : 9 is perfect square of 3, so √9 returns 3

1Example2 :
2
3  Input : 11
4
5  Output: 3
6
7  Explanation : 
8    9 < 11 < 16 => 32 < 11 < 42
9    It means √11 lies between 3 and 4 and so floor(√11) = 3

Solution Approaches

Naïve Solution

Intuition

We know that square root of an integer n always lies between 1 and n.

If k is square root of n, it means k² = n.

So for k ranging from 1 to n, check if k² = n satisfies or not.

This approach is called linear search, searching for k from 1 to n for which k² = n.

If x is not perfect square then the value of x will be the one which satisfies k² < n < (k+1)²

Algorithm

1Input : An integer n
2
3Step 0: Initialize a variable k = 1
4
5Step 1: If n = 0 or n = 1 return n
6
7Step 2: if k*k <=n increment k 
8
9Step 3: else return k-1 
10
11Step 4: Repeat steps 2 to 3.
12
13Output : floor(√n)

Handling Integer Overflow

1Note : Few languages like java, step 2 might cause integer overflow if n is too large
2
3As per problem constraints, the max value of n is 2147483647 ( 2³¹ - 1 ). 
4
5The square root of 2147483647 is 46340, But for n = 2147483647, the loop will not exit even though k crosses 46340. 
6
7The reason is very simple, an incase of java int variable at max can hold value up to 2147483647, and k² for k above 46340 causes integer overflow (eg: 46341² = -2147479015).
8
9To overcome this, convert k² <=n to k <= n/k

Video Explanation

Code Implementation

1public class SquareRootUsingLinearSearch {
2
3    public int squareRoot(int n) {
4        if(n == 0 || n == 1){
5            return n;
6        }
7        int k = 1;
8        // if k*k equals to n then k is the answer
9        // if k*k < n < (k+1) * (k+1) then k is the answer
10        // It means (k+1) * (k+1) > n , k is the answer
11        // As k*k may cause integer overflow convert equation k*k <= n => k <= n/k
12        while (k <= n/k) {
13            k++;
14        }
15        return k-1;
16    }
17
18    public static void main(String[] args){
19        SquareRootUsingLinearSearch obj = new SquareRootUsingLinearSearch();
20        int n = 9;
21        System.out.printf("sqrt(%d) = %d%n", n, obj.squareRoot(n));
22        n = 16;
23        System.out.printf("sqrt(%d) = %d%n", n, obj.squareRoot(n));
24        n = 25;
25        System.out.printf("sqrt(%d) = %d%n", n, obj.squareRoot(n));
26        n = 26;
27        System.out.printf("sqrt(%d) = %d%n", n, obj.squareRoot(n));
28        n = Integer.MAX_VALUE;
29        System.out.printf("sqrt(%d) = %d%n", n, obj.squareRoot(n));
30    }
31}

Complexity Analysis

• Time Complexity : O(√n)
• Space Complexity : O(1)

Using Binary Search

Prerequisite

• Binary Search

Intuition

1We know that square root of an integer n always lies between 1 and n. 
2
3If  k is square root of n, it means k² = n. 
4
5For some k between 1 and n (both 1 and n inclusive), there are three cases possible
6If k² = n then x is the answer
7If k² <n then sqrt(n) lies in between k and n ( k <= sqrt(n) <= n)
8If k² > n then sqrt(n) lies in between 1 and k(1 <= sqrt(n) <= k)
9
10It means that we can find k efficiently by using binary search algorithm.

Algorithm

1Input : An integer n
2
3Step 0: Initialize low as 1 and high as n, and 
4        initialize ans to store square root of n.
5
6Step 1: Repeat below steps until low lesser than or equal to high 
7
8Step 2: compute mid as (low+high)/2
9
10Step 3: If mid*mid equal to n, return mid
11
12Step 4: If mid*mid < n then search between mid+1 to n by updating 
13        low as mid+1 and 
14        update ans = mid (if n is not perfect square, mid might be the answer basis of mid+1)
15
16Step 5: If mid*mid is > n then search between 1 and mid-1 by updating 
17        high as mid-1
18
19Output : floor(√n)

Video Explanation

Code Implementation

1public class SquareRootUsingBinarySearch {
2
3    // method to get square root of given integer
4    public int squareRoot(int n) {
5        if(n == 0 || n == 1){
6            return n;
7        }
8        // Square Root of any number n always lies in the range (1, n)
9        // So initialize low to 1 and high to n
10        int low = 1;
11        int high = n;
12        int ans = -1;
13        while( low <= high){
14
15            // compute mid of low and high
16            // to avoid mid to integer overflow, u can replace mid = low+(high-mid)/2;
17            int mid = (low+high)/2;
18            System.out.println(low +" "+ high +" "+mid + " "+ans);
19            // if mid*mid equals to n then mid is the answer
20            // if mid*mid < n, mid is the answer if (mid+1) * (mid+1) > n => so increase lower bound
21            // If mid*mid > n, increase upper bound of search space
22            // As k*k may cause integer overflow convert equation k*k <= n => k <= n/k
23            if (mid*mid == 0) {
24                return mid;
25            }else if (mid*mid < n) {
26                ans = mid;
27                low = mid+1;
28            }else {
29                high = mid-1;
30            }
31        }
32        System.out.println(low +" "+ high +" " + " "+ans);
33        return ans;
34    }
35
36    public static void main(String[] args){
37        SquareRootUsingBinarySearch obj = new SquareRootUsingBinarySearch();
38        
39        int n = 99;
40        System.out.printf("sqrt(%d) = %d%n", n, obj.squareRoot(n));
41    }
42}

Complexity Analysis

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

Approaches Comparison