 Tagged
• DSA Problems
• Linear Search
• Binary Search
•

# 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 - 17
8Input: An integer n9
10Output: floor(√n)```

```1Example1 :2
3  Input : 94
5  Output: 36
7  Explanation : 9 is perfect square of 3, so √9 returns 3```

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

# 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 n2
3Step 0: Initialize a variable k = 14
5Step 1: If n = 0 or n = 1 return n6
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 large2
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```

## Code Implementation

1. Java
2. Python
3. Go

```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 answer9        // if k*k < n < (k+1) * (k+1) then k is the answer10        // It means (k+1) * (k+1) > n , k is the answer11        // As k*k may cause integer overflow convert equation k*k <= n => k <= n/k12        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

## 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 possible6If k² = n then x is the answer7If 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 n2
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)/29
10Step 3: If mid*mid equal to n, return mid11
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-118
19Output : floor(√n)```

## Code Implementation

1. Java
2. Python
3. Go

```1public class SquareRootUsingBinarySearch {2
3    // method to get square root of given integer4    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 n10        int low = 1;11        int high = n;12        int ans = -1;13        while( low <= high){14
15            // compute mid of low and high16            // 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 answer20            // if mid*mid < n, mid is the answer if (mid+1) * (mid+1) > n => so increase lower bound21            // If mid*mid > n, increase upper bound of search space22            // As k*k may cause integer overflow convert equation k*k <= n => k <= n/k23            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

ApproachTime ComplexitySpace Complexity
Using Linear SearchO(√n)O(1)
Using Binary SearchO( log(n) )O(1)

• DSA Problems
• Linear Search
• Binary Search
•
...