Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16 Output: true

Example 2:

Input: 14 Output: false

Solution

We know that for any number its square value is always more than its double value, We can take advantage of it. For given number its square root value lies between 1 to num/2. Apply binary search approach between 1 to num/2 and check for all mid elements.

Code

Output

true

Complexity Analysis

Time complexity: O(log n).
Space Complexity: O(1).

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *