Checking for a full square
It’s possible to do a binary search on any ordered list: be it a list of increasing heights, integer numbers, floating-point numbers, etc. It can even be the set of integers , the set of natural numbers , or the set of rational numbers . We would still pick a range of possible solutions and throw away the unnecessary part on each iteration.
Challenge
Given a positive integer
n, you are asked to check if it’s a full square without using the sqrt function.Input
The input contains a single integer
n (2 ≤ n ≤ ).Output
The program should print
Yes if n is a full square and No otherwise.Examples
Input | Output |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Hint
If
n is a full square ⇒ there is another number x that x on an interval [1, 2, …, n].Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB