456. Valid Perfect Square (BS Approach)

Given a positive integer num, return true if it is a perfect square, false otherwise. A perfect square is an integer that is the square of another integer. Do not use built-in sqrt functions. Solve in O(log n).

Input: A positive integer num.

Output: true if num is a perfect square, false otherwise.

Examples

Input: 16
Output: true
Explanation: 4*4=16.

Input: 14
Output: false
Explanation: No integer r with r*r=14.

Input: 1
Output: true
Explanation: 1*1=1.

Constraints

• 1 <= num <= 2^31 - 1

Asked by