Objective: Given an integer check whether it is a perfect square.
Example:
number = 37 Output: false number = 49 Output: true
This is fun puzzle which is asked in the interview.
Approach:
- Say number is n.
- Start a loop from 1 to n/2.
- During iteration, for every integer ‘i’, calculate x = i*i.
- Now with this ‘x’ there are 3 possibilities.
- If x == n then n is a perfect square, return true
- If x > n then x has crossed the n, n is not perfect square. Return false
- If above step a or b are not true then continue.
Time Complexity: O(sqrt(n))
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class ValidateSquare { | |
| public static boolean isSquare(int n){ | |
| if(n==0 || n==1) | |
| return true; | |
| for (int i = 0; i <=n/2 ; i++) { | |
| int x = i*i; | |
| if(x==n) | |
| return true; | |
| else if (n<x) | |
| return false; | |
| else | |
| continue; | |
| } | |
| return false; | |
| } | |
| public static void main(String[] args) { | |
| int n = 37; | |
| System.out.println(n + " is square: " + isSquare(n)); | |
| n = 49; | |
| System.out.println(n + " is square: " + isSquare(n)); | |
| } | |
| } |
Output:
37 is square: false 49 is square: true
How about number 1? 1 is a perfect square. The above implementation will return false.