Given a number N, the task is to find the square root of N without using sqrt() function.
Examples:
Input: N = 25
Output: 5Input: N = 3
Output: 1.73205Input: N = 2.5
Output: 1.58114
Approach 1:
We can consider (?x-?x)2 = 0.
Replacing one of the ?x‘s with y, then the equation becomes (y-?x)2 => y2 – 2y?x + x = 0
=> ?x = (y2 + x) / 2y
=> ?x = (y + x/y) / 2In the above equation, we are considering ?x as z.
So, to get a required decimal value we can compare the difference of y and z to 10-p (to get the result upto 5 decimal digits, compare y-z to 10-5=0.00001). Until y-z exceeds it, the iteration continues.
Below is the implementation of the above idea:
C
// C Program to find square// root of a number#include <stdio.h>#include <stdlib.h>#include <math.h>double findSqrt(double x){ // for 0 and 1, the square roots are themselves if (x < 2) return x; // considering the equation values double y = x; double z = (y + (x / y)) / 2; // as we want to get upto 5 decimal digits, the absolute // difference should not exceed 0.00001 while (fabs(y - z) >= 0.00001) { y = z; z = (y + (x / y)) / 2; } return z;}int main(){ double n = 3; double ans = findSqrt(n); printf("%.5f is the square root of 3\n", ans); return 0;} |
C++
// C++ Program to find square// root of a number#include <bits/stdc++.h>using namespace std;double findSqrt(double x){ // for 0 and 1, the square roots are themselves if (x < 2) return x; // considering the equation values double y = x; double z = (y + (x / y)) / 2; // as we want to get upto 5 decimal digits, the absolute // difference should not exceed 0.00001 while (abs(y - z) >= 0.00001) { y = z; z = (y + (x / y)) / 2; } return z;}int main(){ double n = 3; double ans = findSqrt(n); cout << setprecision(6) << ans << " is the square root of 3" << endl; return 0;} |
Java
/// Java Program to find square// root of a numberimport java.io.*;import java.util.*;class GFG { public static double findSqrt(double x) { // for 0 and 1, the square roots are themselves if (x < 2) return x; // considering the equation values double y = x; double z = (y + (x / y)) / 2; // as we want to get upto 5 decimal digits, the // absolute difference should not exceed 0.00001 while (Math.abs(y - z) >= 0.00001) { y = z; z = (y + (x / y)) / 2; } return z; } public static void main(String[] args) { double n = 3; double ans = findSqrt(n); System.out.println(String.format("%.5f", ans) + " is the square root of 3"); }} |
Python3
# Python Program to find square# root of a numberdef findSqrt(x): # for 0 and 1, the square roots are themselves if x < 2: return x # considering the equation values y = x z = (y + (x/y)) / 2 # as we want to get upto 5 decimal digits, the absolute difference should not exceed # 0.00001 while abs(y - z) >= 0.00001: y = z z = (y + (x/y)) / 2 return z if __name__ == '__main__': n = 323242 ans = findSqrt(n) print(ans) |
C#
// C# Program to find square// root of a numberusing System;using System.Collections.Generic;public class GFG { public static double findSqrt(double x) { // for 0 and 1, the square roots are themselves if (x < 2) return x; // considering the equation values double y = x; double z = (y + (x / y)) / 2; // as we want to get upto 5 decimal digits, the // absolute difference should not exceed 0.00001 while (Math.Abs(y - z) >= 0.00001) { y = z; z = (y + (x / y)) / 2; } return z; } static public void Main() { double n = 3; double ans = findSqrt(n); ans = Math.Round(ans, 5); Console.WriteLine(ans + " is the square root of 3"); }} |
Javascript
// Javascript Program to find square// root of a number function findSqrt(x){ if(x < 2){ return x; } let y = x; let z = (y + (x/y))/2; while(Math.abs(y-z)>=0.00001){ y = z; z = (y + (x/y))/2; } return z; } let n = 3; let ans = findSqrt(n); console.log(ans.toPrecision(6) + " is the square root of 3"); |
Output
1.73205 is the square root of 3
Time Complexity: O(log N)
Auxiliary Space: O(1)
Approach 2:
- Start iterating from i = 1. If i * i = n, then print i as n is a perfect square whose square root is i.
- Else find the smallest i for which i * i is strictly greater than n.
- Now we know square root of n lies in the interval i – 1 and i and we can use Binary Search algorithm to find the square root.
- Find mid of i – 1 and i and compare mid * mid with n, with precision upto 5 decimal places.
- If mid * mid = n then return mid.
- If mid * mid < n then recur for the second half.
- If mid * mid > n then recur for the first half.
Below is the implementation of the above approach:
C
// C implementation of the approach#include<stdio.h>#include<math.h>#include <stdbool.h>// Recursive function that returns square root// of a number with precision upto 5 decimal placesdouble Square(double n, double i, double j){ double mid = (i + j) / 2; double mul = mid * mid; // If mid itself is the square root, // return mid if ((mul == n) || (fabs(mul - n) < 0.00001)) return mid; // If mul is less than n, recur second half else if (mul < n) return Square(n, mid, j); // Else recur first half else return Square(n, i, mid);}// Function to find the square root of nvoid findSqrt(double n){ double i = 1; // While the square root is not found bool found = false; while (!found) { // If n is a perfect square if (i * i == n) { printf("%.0lf",i); found = true; } else if (i * i > n) { // Square root will lie in the // interval i-1 and i double res = Square(n, i - 1, i); printf("%.5lf", res); found = true; } i++; }}// Driver codeint main(){ double n = 3; findSqrt(n); return 0;} |
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Recursive function that returns square root// of a number with precision upto 5 decimal placesdouble Square(double n, double i, double j){ double mid = (i + j) / 2; double mul = mid * mid; // If mid itself is the square root, // return mid if ((mul == n) || (abs(mul - n) < 0.00001)) return mid; // If mul is less than n, recur second half else if (mul < n) return Square(n, mid, j); // Else recur first half else return Square(n, i, mid);}// Function to find the square root of nvoid findSqrt(double n){ double i = 1; // While the square root is not found bool found = false; while (!found) { // If n is a perfect square if (i * i == n) { cout << fixed << setprecision(0) << i; found = true; } else if (i * i > n) { // Square root will lie in the // interval i-1 and i double res = Square(n, i - 1, i); cout << fixed << setprecision(5) << res; found = true; } i++; }}// Driver codeint main(){ double n = 3; findSqrt(n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Recursive function that returns // square root of a number with // precision upto 5 decimal placesstatic double Square(double n, double i, double j){ double mid = (i + j) / 2; double mul = mid * mid; // If mid itself is the square root, // return mid if ((mul == n) || (Math.abs(mul - n) < 0.00001)) return mid; // If mul is less than n, // recur second half else if (mul < n) return Square(n, mid, j); // Else recur first half else return Square(n, i, mid);}// Function to find the square root of nstatic void findSqrt(double n){ double i = 1; // While the square root is not found boolean found = false; while (!found) { // If n is a perfect square if (i * i == n) { System.out.println(i); found = true; } else if (i * i > n) { // Square root will lie in the // interval i-1 and i double res = Square(n, i - 1, i); System.out.printf("%.5f", res); found = true; } i++; }}// Driver codepublic static void main(String[] args) { double n = 3; findSqrt(n);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approachimport math# Recursive function that returns square root# of a number with precision upto 5 decimal placesdef Square(n, i, j): mid = (i + j) / 2; mul = mid * mid; # If mid itself is the square root, # return mid if ((mul == n) or (abs(mul - n) < 0.00001)): return mid; # If mul is less than n, recur second half elif (mul < n): return Square(n, mid, j); # Else recur first half else: return Square(n, i, mid);# Function to find the square root of ndef findSqrt(n): i = 1; # While the square root is not found found = False; while (found == False): # If n is a perfect square if (i * i == n): print(i); found = True; elif (i * i > n): # Square root will lie in the # interval i-1 and i res = Square(n, i - 1, i); print ("{0:.5f}".format(res)) found = True i += 1;# Driver codeif __name__ == '__main__': n = 3; findSqrt(n);# This code is contributed by 29AjayKumar |
C#
// C# implementation of the approachusing System; class GFG {// Recursive function that returns // square root of a number with // precision upto 5 decimal placesstatic double Square(double n, double i, double j){ double mid = (i + j) / 2; double mul = mid * mid; // If mid itself is the square root, // return mid if ((mul == n) || (Math.Abs(mul - n) < 0.00001)) return mid; // If mul is less than n, // recur second half else if (mul < n) return Square(n, mid, j); // Else recur first half else return Square(n, i, mid);}// Function to find the square root of nstatic void findSqrt(double n){ double i = 1; // While the square root is not found Boolean found = false; while (!found) { // If n is a perfect square if (i * i == n) { Console.WriteLine(i); found = true; } else if (i * i > n) { // Square root will lie in the // interval i-1 and i double res = Square(n, i - 1, i); Console.Write("{0:F5}", res); found = true; } i++; }}// Driver codepublic static void Main(String[] args) { double n = 3; findSqrt(n);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Recursive function that returns// square root of a number with// precision upto 5 decimal placesfunction Square(n, i, j){ var mid = ((i + j) / 2); var mul = mid * mid; // If mid itself is the square root, // return mid if ((mul == n) || (Math.abs(mul - n) < 0.00001)) return mid; // If mul is less than n, // recur second half else if (mul < n) return Square(n, mid, j); // Else recur first half else return Square(n, i, mid);}// Function to find the square root of nfunction findSqrt(n){ var i = 1; // While the square root is not found var found = false; while (!found) { // If n is a perfect square if (i * i == n) { document.write(i); found = true; } else if (i * i > n) { // Square root will lie in the // interval i-1 and i var res = Square(n, i - 1, i); document.write(res.toFixed(5)); found = true; } i++; }}// Driver codevar n = 3;findSqrt(n);// This code is contributed by todaysgaurav</script> |
Output
1.73205
Time complexity: O(log N) where N is the given integer.
Auxiliary space: O(log N) for recursive stack space.
Method 3: Using binary search
1. This method uses binary search to find the square root of a number.
2. It starts by initializing the search range from 1 to n. It then calculates the mid-point of the search range and checks if the square of the mid-point is equal to the number we want to find the square root of.
3. If it is, the mid-point is the square root of the number. If not, the search range is updated based on whether the square of the mid-point is less than or greater than the number we want to find the square root of.
4. This process continues until we find the square root of the number.
C++
#include <iostream>using namespace std;int sqrt(int n) { if (n < 2) { return n; } int low = 1, high = n; while (low <= high) { int mid = (low + high) / 2; if (mid * mid == n) { return mid; } else if (mid * mid < n) { low = mid + 1; } else { high = mid - 1; } } return high;}int main() { int n = 25; cout << sqrt(n) << std::endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class Main { public static int sqrt(int n) { if (n < 2) { return n; } int low = 1, high = n; while (low <= high) { int mid = (low + high) / 2; if (mid * mid == n) { return mid; } else if (mid * mid < n) { low = mid + 1; } else { high = mid - 1; } } return high; } public static void main(String[] args) { int n = 25; System.out.println(sqrt(n)); } } |
Python3
def sqrt(n): if n < 2: return n low, high = 1, n while low <= high: mid = (low + high) // 2 if mid * mid == n: return mid elif mid * mid < n: low = mid + 1 else: high = mid - 1 return highn=25print(sqrt(n)) |
C#
using System;class Program { static int Sqrt(int n) { if (n < 2) { return n; } int low = 1, high = n; while (low <= high) { int mid = (low + high) / 2; if (mid * mid == n) { return mid; } else if (mid * mid < n) { low = mid + 1; } else { high = mid - 1; } } return high; } static void Main(string[] args) { int n = 25; Console.WriteLine(Sqrt(n)); }} |
Javascript
function sqrt(n) { if (n < 2) { return n; } let low = 1, high = n; while (low <= high) { let mid = Math.floor((low + high) / 2); if (mid * mid === n) { return mid; } else if (mid * mid < n) { low = mid + 1; } else { high = mid - 1; } } return high;}let n = 25;console.log(sqrt(n)); // expected output: 5 |
Output
5
Time complexity:
The time complexity of this algorithm is O(log n) since it uses binary search to find the square root of a number.
Auxiliary space:
The algorithm does not use any extra space, so the space complexity is O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
