...

/

Calculate Square Root of a Number

Calculate Square Root of a Number

Given a non-negative double number, write a function to calculate its square root.

Statement

Given a number of type double, calculate its square root.

Constraints

For this problem, the given number is always a non-negative double number.

Example

Sample input

16.0

Expected output

4.0

Try it yourself

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
// EPSILON is used to denote a small quantity, like an error,
// or perhaps a term which will be taken to zero in some limit
const double EPSILON = 0.00001;
double SquareRoot(double num) {
// TODO: Write - Your - Code
return num;
}

Solution 1

We pass both low and high values to each recursive function call, where mid and square is calculated.

  • If the square of mid is equal to n then it is the base case, and we return mid as the square root of n.

  • If the square of mid is smaller than n then in the next recursive call, low is changed to mid and high remains unchanged.

  • If the square of mid is larger than n then in the next recursive call, high is changed to mid and low remains unchanged.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
// EPSILON is used to denote a small quantity, like an error,
// or perhaps a term which will be taken to zero in some limit
const double EPSILON = 0.00001;
double SquareRootRec(double num, double low, double high) {
double mid = (low + high) / 2;
double sqr = mid * mid;
// Finds the difference between the calculated square and given number
double diff = abs(sqr - num);
// we can't do a == b for doubles because
// of rounding errors, so we use error threshold
// EPSILON. Two doubles a and b are equal if
// abs(a-b) <= EPSILON
if (diff <= EPSILON) {
return mid;
}
// If the square of mid is smaller than num, then in the next recursive call,
// low will be changed to mid and high remains unchanged.
if (sqr < num) {
return SquareRootRec(num, mid, high);
}
// Otherwise, that is, if the square of mid is greater than num, then,
// in the next recursive call, high will be changed to mid and
// low remains unchanged.
return SquareRootRec(num, low, mid);
}
double SquareRoot(double num) {
if (num < 0) {
return -1;
} else {
// Calls recursive function with given number, low and high
return SquareRootRec(num, 0, 1 + num / 2);
}
}
int main() {
vector<double> arr = {-16, 17, 2.25};
for (int i = 0; i < arr.size(); i++) {
double ans = SquareRoot(arr[i]);
string ansStr = (ans == -1) ? " Number is negative." : to_string(ans);
cout << i + 1 << ". Square root of " << arr[i] << ": " << ansStr << endl;
cout << "\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n" << endl;
}
}

Time complexity

The time complexity of this solution is logarithmic, O(logn)O(log n).

Space complexity

The space complexity of this solution is logarithmic, O(logn)O(log n).

Solution 2

We can use an algorithm very similar to binary search to find the square root of a number. We know that the square root of a negative number can’t be defined without using complex numbers. As the problem is limited to non-negative numbers only, we will focus on that. It is a good idea to discuss this case with your interviewer.

Let’s assume that the given number is nn and we have to find its square root, ss. Below are two known mathematical facts.

  • The square root of a number is always smaller than the given number if the number is greater than 1.

1<=s<n,ifn>=11<=s<n, \:if\: n>=1 ...