Real O(1) just for fun


  • 0
    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
    

  • 0

    This is a smart solution! Good job, man.


  • 0
    S

    Interesting.......


  • 0
    T

    Can someone explain how this works?!


  • 1

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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.