Description
https://leetcode.com/problems/valid-perfect-square/
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Follow up: Do not use any built-in library function such as sqrt.
Example 1:
Input: num = 16 Output: true
Example 2:
Input: num = 14 Output: false
Constraints:
1 <= num <= 2^31 - 1
Explanation
Use binary search to search between 1 and num // 2 if any number which has the square value equal to num
Python Solution
class Solution:
def isPerfectSquare(self, num: int) -> bool:
start = 1
end = num // 2
while start + 1 < end:
mid = start + (end - start) // 2
if mid * mid < num:
start = mid
elif mid * mid > num:
end = mid
else:
return True
if end * end != num and start * start != num:
return False
return True- Time Complexity: O(log(N)).
- Space Complexity: O(1).