Given a positive number, find square root of it. If the number is not a perfect square, then return floor of its square root.
Input: x = 12
Output: 3
Input: x = 16
Output: 4
Naive solution is to consider all positive numbers starting from 1, and find the first number i for which i*i is greater than the given number x. Then, i-1 would be the floor of square root of x.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <stdio.h> // Function to find floor of square root of x int sqrt(int x) { // find first positive number i such that i*i is greater than x int i = 1; while (i*i <= x) i++; return i - 1; } int main(void) { for (int i = 0; i <= 16; i++) printf("sqrt(%d) = %d\n", i, sqrt(i)); return 0; } |
The time complexity of above solution is O(√x). We can improve the time complexity to O(log(x)) with the help of binary search algorithm. The algorithm can be implemented as follows in C:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <stdio.h> // Function to find square root of x using binary search algorithm // If x is not a perfect square, return floor of the square root int sqrt(int x) { // base case if (x < 2) return x; // to store floor of sqrt(x) int result; // square root of x cannot be more than x/2 for x > 1 int start = 1; int end = x/2; while (start <= end) { // find mid element int mid = (start + end) / 2; long sqr = mid*mid; // return mid if x is a perfect square if (sqr == x) return mid; // if mid*mid is less than x else if (sqr < x) { // discard left search space start = mid + 1; // update result since we need floor result = mid; } // if mid*mid is more than x else { // discard right search space end = mid - 1; } } // return result return result; } int main(void) { for (int i = 0; i <= 16; i++) printf("sqrt(%d) = %d\n", i, sqrt(i)); return 0; } |
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Recursive solution to this problem:
int sqrt(int num, int so_far, int s, int e){
if( s <= e){
int mid = (s+e)/2;
if( mid * mid == num) return mid;
else if(mid*mid < num){
so_far = mid;
return sqrt(num,so_far,mid+1, e);
}else return sqrt(num, so_far,s, mid-1);
}
return so_far;
}