Difficulty: Medium, Asked-In: Amazon, Microsoft, Facebook
Key takeaway: An excellent problem to learn problem-solving using binary search.
Square Root problem
Given a natural number n, find the largest integer that is less than or equal to √n. This can be seen as a search problem where the search space S is the set {1, . . . , n}, and the number desired is the floor(√n), i.e., the largest integer that is less than or equal to √n.
Examples
Input: n = 9, Output: 3
Explanation: The square root of 9 is 3.
Input: n = 14, Output: 3
Explanation: The square root of 14 lies between 3 and 4. So the largest integer that is less than or equal to √14 is 3.
Brute Force Approach
One basic idea would be to check all integers starting from k = 1. If the square of the integer k is less than the given number n, then we move to the next integer. We continue this process of integer increment until the square of the integer k is greater than n. In other words, we stop when k^2 < n.
Solution Steps
- We take care of some base cases i.e. when n is 0 or 1, we return n.
- Otherwise, we initialize a variable k = 1
- Now we run a loop until k^2 <= n, where we increment the variable k by 1.
- By end of the loop, the floor of the square root of n is k - 1.
Solution Pseudocode
int findSquareRoot(int n)
{
if (n <= 1)
return n
int k = 1
while (k*k <= n)
k = k + 1
return k - 1
}
Complexity analysis
Here loop is running till k^2 <= n and at each iteration, we are doing constant operations. So total number of loop iterations = √n. So time complexity = √n * O(1) = O(√n)
An efficient approach using binary search
Solution Idea
The main idea behind this algorithm is to use binary search to find the largest integer whose square is less than or equal to n.
The algorithm maintains low and high values, which are initialized to 1 and n, respectively. We check if the mid-point value, mid = (low + high)/2 is the desired answer, by checking whether (mid ∗ mid <= n) and ((mid + 1) ∗ (mid + 1) > n). If mid is not the answer, the desired answer is either less than mid or greater than mid. So depending on whichever the situation is, the low or high values are set to mid accordingly.
Solution Steps
- We take care of some base cases, i.e when the given number is 0 or 1.
- We initialize the loop variables low = 0 and high = n.
- Now we run a loop until low <= high. At each step of the iteration:
- We calculate the mid-value i.e. mid = (low + high)/2
- If (mid * mid <= n and (mid + 1) * (mid + 1) > n), then this is our desired answer and we return the mid-value.
- If (mid*mid <= n), then our desired answer would be present in the right half of the search space. So we update low = mid + 1.
- Otherwise, our desired answer would be present in the left half of the search space. So we update high = mid - 1.
Solution Pseudocode
int findSquareRoot(int n)
{
if (n <= 1)
return n
int low = 1, high = n
while (low <= high)
{
int mid = (low + high)/2
if (mid * mid <= n && (mid + 1) * (mid + 1) > n)
return mid
else if (mid*mid <= n)
low = mid + 1
else
high = mid - 1
}
}
Complexity analysis
Binary search reduces the search space by approximately half in each iteration. If the search space is of size n initially, then in the first iteration, it becomes at most n/2, and in the next iteration, it becomes at most n/4 = n/2^2, and then in the next, it becomes n/8 = n/2^3 and so on. Hence, by logn iterations, the size is at most n/2^log n = 1.
Thus after logn iterations, the search space has reduced to at most 1. In other words: we would have found the answer by the end of logn iterations. We converge to the desired solution in at most logn number of steps, and at each step, we perform O(1) operations. So time complexity = logn * O(1) = O(logn). Note: here, logn is the logarithm of n to base 2, i.e., log2 n.
Extended Square Root: find the value of the square root up to a given precision using a binary search
In the above algorithm, we have discussed how to compute the integral value of the square root of a number n. We need to find the square root of a number up to p decimal places using binary search. So the critical question is: how do we modify the above code to calculate this? Let's think!
In the above code, whenever mid * mid <= n and (mid + 1) * (mid + 1) > n, we are returning mid as the integer part of the square root. So we can do little modifications and, instead of returning mid, we pass it to a function sqrtPrecision(mid, n, p) which returns the square root of n up to p decimal places.
Inside the sqrtPrecision(mid, n, p) function, we initialize the increment variable by 0.1 and iteratively compute the fractional part up to p places. The increment changes to 1/10th of its previous value in each iteration, and we get the answer at the end of the loop.
Solution Pseudocode
void findSquareRoot(int n, int p)
{
if (n <= 1)
return n
int low = 1, high = n
while (low <= high)
{
int mid = (low + high)/2
if (mid * mid <= n && (mid + 1) * (mid + 1) > n)
return sqrtPrecision(mid, n, p)
else if (mid*mid <= n)
low = mid + 1
else
high = mid - 1
}
}
float sqrtPrecision(int squareRoot, int n, int p)
{
float decimalValue = 0.1
for (int i = 0; i < p; i = i + 1)
{
while (squareRoot * squareRoot <= n)
squareRoot = squareRoot + decimalValue
squareRoot = squareRoot - decimalValue
decimalValue = decimalValue / 10
}
return squareRoot
}
Complexity analysis
Time complexity = Time complexity of finding integral part + Time complexity of calculating decimal part up to p precision = O(logn) + O(p) = O(logn + p)
Critical Ideas to Think!
- Can we try to implement the binary search approach using some other idea?
- Can we try to optimize the binary search approach further?
- Sometimes multiplication of mid*mid or (mid + 1)*(mid + 1) can be very large, which may cause integer overflow. How can we handle such a scenario in the binary search approach?
- Explore the Babylonian and other methods for finding the square root
- Explore the various mathematical properties of square roots
Suggested blogs to explore
Note: Gradually we will update more exciting content to this blog!
Enjoy learning, enjoy mathematics!