How to check valid perfect square without sqrt (in-built Library function).
Given a positive integer, We have to write a code to returns true if it is a perfect square else false.
For solving this problem, we don’t have to use any built-in library function (such as sqrt).
For Example –
Example 1:
Input: 36
output: true
Example 2:
Input: 17
output: false
Example 3:
Input: 1
output: true
In this tutorial, I am going to discuss multiple approaches to solve this problem.
The simplest approach to solve this problem is by running a loop from 1 to n, where n is the input number. In each iteration do the square of a number and compare with the input number n. If it is equal then return true else return false.
Is there any better way to solve this problem? Yes let’s discuss it.
Valid Perfect Square without Sqrt – Java Code
We can solve this problem by using a property that the square root of a number lies between 2 to n/2.
It means if a number is less than 2 then simply return true. Otherwise run a loop from 2 to n/2. At each step do the square and compare with input number. If it’s equal to number then return true. If the square of a number is greater than the input number then return false.
|
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 |
//Check perfect square using binary search public class ValidPerfectSquare { public static boolean isPerfectSquare(int num) { if(num < 2) return true; for(int i = 2; i <= num/2; i++) { if((i*i) == num) { return true; } else if ((i*i) > num) { return false; } } return false; } public static void main(String[] args) { System.out.println(isPerfectSquare(16)); } } |
Valid Perfect Square using Binary Search – Java Code
Given a number n, We know square root of n lies between 2 and n/2. Using this property we can solve this problem using Binary Search.
In this approach, we first calculate the mid using start and end variable. Then we check square of mid is equal to n. If it’s then it’s a valid perfect square.
Else if square of mid is greater than n then we assign mid-1 to end variable. If square of mid is smaller than n then we assign mid+1 to start.
The time complexity of this approach is O(logn).
Programming questions on Binary Search
|
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 |
//Check perfect square using binary search public class ValidPerfectSquare { public static boolean isPerfectSquare(int num) { if(num < 2) return true; long start = 2; long end = num/2; while(start <= end) { //To prevent overflow long mid = start + (end - start) / 2; if(mid*mid == num) { return true; } else if (mid*mid > num) { end = mid - 1; } else { start = mid+1; } } return false; } public static void main(String[] args) { System.out.println(isPerfectSquare(16)); } } |
