Last Updated: 9 Jan, 2021

Valid Perfect Square

Easy

Asked in companies

Solve now

Problem statement

You have been given an integer ‘N’. You are supposed to find if the given integer ‘N’ is a perfect square or not. A perfect square is an integer that is the square of an integer.

Input Format:

The first line contains an integer ‘T’ denoting the number of test cases. 

The first input line of each test case contains an integer ‘N’ denoting the input integer.

Output Format:

For each test case, return “true/Yes” if the given number is a perfect square otherwise return “false/No”.

Note:

You don't have to print the output, it has already been taken care of. Just implement the given function.

Follow up:

Try to do it without using built-in library functions like sqrt().

Constraints:

1 <= T <= 50
1 <= N <= 10^18

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea of this approach is to iterate through every possible integer that could be the square root of the given number. We can terminate the loop when we have found the square root or when the squared value is greater than the given number.

The steps are as follows:

Start iterating using a variable ‘i’ such that 1 <= i * i <= ‘N’
- Check if ‘i’ is the square root of the given number i.e. if (i * i == ‘N’) then ‘N’ is a perfect square. So return true.
Return false because ‘N’ is not a perfect square.

Solve now

02 Approach

The basic idea of this approach is to do a binary search to find the square root of the given number if it exists.

The steps are as follows:

Create and initialize two variables ‘low’ and ‘high’ to 1 and 10^4 respectively. ['low', ‘high’] denotes the range of possible values of the square root.
Now, loop while ‘low’ is less than or equal to ‘high’:
- Assign ‘mid’ = ('low' + ‘high’) / 2
- Check if ‘mid’ is the perfect square. If it is, then return true.
- Otherwise, check if the square of ‘mid’ is greater than the given number ‘N’. If it is, then any number less than ‘mid’ can have the chance of being the square root. So adjust the upper limit of the search space to ‘mid' - 1 i.e. ‘high’ = ‘mid’ - 1
- Similarly, if the square of ‘mid’ is smaller than the given number ‘N’, then any number greater than the ‘mid’ can have the chance of being the square root. So adjust the lower limit of the search space to 'mid' + 1 i.e. 'low' = 'mid' + 1
Finally, return false if ‘N’ is not a perfect square.

Solve now