Valid Perfect Square

Easy
0/40
Average time to solve is 10m
profile
Contributed by
30 upvotes
Asked in companies
HSBCReliance Jio Infocomm LtdCIS - Cyber Infrastructure

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
7
Sample output 1:
Yes
No
Explanation of Sample Output 1:
In test case 1, since (2 * 2 == 4) so print “Yes”.

In test case 2, 7 is not a perfect square so print “No”.
Sample Input 2:
2
15
121
Sample output 2:
No
Yes
Explanation of Sample Output 2:
In test case 1, 15 is not a perfect square so print “No”.

In test case 2, since (11 * 11 == 121) so print “Yes”.
Hint

Can you think of checking every possible square root?

Approaches (2)
Naive 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:

 

  1. 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.
  2. Return false because ‘N’ is not a perfect square.
Time Complexity

O(sqrt(N)), Where ‘N’ is the given integer.

 

Since we are running a for loop for at max sqrt(N) times. And then doing some operations at each iteration which takes O(1) time. Thus the overall time complexity will be O(sqrt(N)).

Space Complexity

O(1).

 

Since we are not using any extra space. Thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Valid Perfect Square
Full screen
Console