class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
r = num
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
r = (r + num / r) / 2
return r * r == num
Real O(1) just for fun


@takirala It's Newton Approximation. Twentish iterations can ensure returning the correct answer. This is just for fun.