Find Square Root of an Integer. How to calculate square root in java without sqrt function.
Given an integer x (non-negative integer). Write a code to compute the square root of x.
If x is not a perfect square in that case return floor of square root of x (floor(sqrt(x))).
NOTE: Do not use the sqrt function from the standard library.
For example –
Example 1:
Input: 4
Output: 2
Example 2:
Input: 11
Output: 3
The square root of 11 is 3.316624 but we have returned the integer part only after truncating the decimal digits.
floor(3.316624) is 3
Example 3:
Input: 17
Output: 4
The square root of 17 is 4.12310. Floor(4.12310) is 4.
In this tutorial, I am going to discuss multiple approaches and their time complexities.
Find Square Root of a Number without using sqrt Function – Java Code
The simplest approach to solve this problem is to try all numbers starting from 1.
Do the square of every number and compare it with the input value. If the square is smaller the input number. In that case, increment the number else return the current number-1.
The time complexity of this approach is O(Sqrt(n)).
|
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 |
/* Find square root of a number without using library function */ public class SquareRoot { public static int findSqrt(int x) { if(x < 2) { return x; } int p = 1; while(p*p <= x) { p++; } return p-1; } public static void main(String[] args) { System.out.println(findSqrt(11)); } } |
Find Square Root of an Integer using Binary Search – Java Code
In our previous approach, we tried all the numbers starting from 1. We can improve our previous approach by using binary search.
The time complexity of this approach is O(logn).
|
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 |
//Find square root of a number using binary search public class SquareRoot { public static int findSqrtUsingBinarySearch(int x) { if(x < 2) { return x; } int start = 1; int end = x; while(start <= end) { int mid = (start + end)/2; if(mid*mid == x) { return mid; } else if (mid*mid > x) { end = mid - 1; } else { start = mid + 1; } } return end; } public static void main(String[] args) { System.out.println(findSqrtUsingBinarySearch(11)); } } |
