Problem statement

https://leetcode.com/problems/valid-perfect-square/

Solution

Simple approach is to check for all numbers k if k^2 = num. Complexity is O(sqrt{n}). Smarter approach is Binary Search with O(log n) complexity.

Complexity

It is O(log n) for time and O(1) for space

Code

class Solution:
    def isPerfectSquare(self, num):
        beg, end = 1, num
        while end - beg  > 1:
            mid = (beg + end)//2
            if mid*mid > num:
                end = mid
            else:
                beg = mid
                
        return beg*beg == num