![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Square Root of an Integer
Problem Statement
1Problem Description : Given a non negative integer n, find the largest integer that is less than or equal to √n. It means2if n is not a perfect square return floor(√n).34NOTE : Do not use sqrt function from standard library.56Constraints: 0 <= n <= 231 - 178Input: An integer n910Output: floor(√n)
1Example1 :23 Input : 945 Output: 367 Explanation : 9 is perfect square of 3, so √9 returns 3
1Example2 :23 Input : 1145 Output: 367 Explanation :8 9 < 11 < 16 => 32 < 11 < 429 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 n23Step 0: Initialize a variable k = 145Step 1: If n = 0 or n = 1 return n67Step 2: if k*k <=n increment k89Step 3: else return k-11011Step 4: Repeat steps 2 to 3.1213Output : floor(√n)
Handling Integer Overflow
1Note : Few languages like java, step 2 might cause integer overflow if n is too large23As per problem constraints, the max value of n is 2147483647 ( 2³¹ - 1 ).45The square root of 2147483647 is 46340, But for n = 2147483647, the loop will not exit even though k crosses 46340.67The 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).89To overcome this, convert k² <=n to k <= n/k
Video Explanation
Code Implementation
- Java
- Python
- Go
1public class SquareRootUsingLinearSearch {23 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 }1718 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
Intuition
1We know that square root of an integer n always lies between 1 and n.23If k is square root of n, it means k² = n.45For 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)910It means that we can find k efficiently by using binary search algorithm.
Algorithm
1Input : An integer n23Step 0: Initialize low as 1 and high as n, and4 initialize ans to store square root of n.56Step 1: Repeat below steps until low lesser than or equal to high78Step 2: compute mid as (low+high)/2910Step 3: If mid*mid equal to n, return mid1112Step 4: If mid*mid < n then search between mid+1 to n by updating13 low as mid+1 and14 update ans = mid (if n is not perfect square, mid might be the answer basis of mid+1)1516Step 5: If mid*mid is > n then search between 1 and mid-1 by updating17 high as mid-11819Output : floor(√n)
Video Explanation
Code Implementation
- Java
- Python
- Go
1public class SquareRootUsingBinarySearch {23 // 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){1415 // 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 }3536 public static void main(String[] args){37 SquareRootUsingBinarySearch obj = new SquareRootUsingBinarySearch();3839 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
Approach | Time Complexity | Space Complexity |
---|---|---|
Using Linear Search | O(√n) | O(1) |
Using Binary Search | O( log(n) ) | O(1) |