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.

1 / 12
#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, ...

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.