Check Perfect Square

Binary SearchMath

Given a non-negative integer n, determine whether it is a perfect square. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.

For example, 1, 4, 9, and 16 are perfect squares while 3, 10, and 17 are not.

Example 1

Input

[
  1
]

Output

true

Explanation. 1 is 1 squared (1x1), therefore it is a perfect square.

Example 2

Input

[
  16
]

Output

true

Explanation. 16 is 4 squared (4x4), therefore it is a perfect square.

Example 3

Input

[
  14
]

Output

false

Explanation. 14 cannot be expressed as the square of any integer.

Example 4

Input

[
  25
]

Output

true

Explanation. 25 is 5 squared (5x5), therefore it is a perfect square.

Example 5

Input

[
  26
]

Output

false

Explanation. 26 cannot be expressed as the square of any integer.

Follow-up: Can this problem be solved without using the built-in square root function? What would be the implications of that approach on the complexity of the algorithm?

Constraints:

Input will be a non-negative integer.

Views: 4