Sqrt: Why memory error on OJ


  • 1
    K

    I try to solve this problem using FOR loop. The code can run successfully on local IDLE( Python 3.4) and give correct answers, but it will raise Memory Error when running on OJ. What is the problem?

    class Solution:
    # @param x, an integer
    # @return an integer
    def sqrt(self, x):
        if x == 0:
            return 0
        elif x == 1:
            return 1
        else:
            # The following line may raise Memory Error
            # The Input is 2147395599
            for i in range(int(x/2) + 1):
                if (i + 1)*(i + 1) < x:
                    continue
                upper_limit = (i + 1)*(i + 1) - x
                lower_limit = x - i*i
                if upper_limit > lower_limit:
                    return i
                else:
                    return i + 1

  • 2
    X

    For anyone who also seek answers here, try use xrange not range,

    Read from other post:

    xrange() generates numbers on demand, which is similar to "for loop" in java/c++; range() pre-computes all numbers and saves in memory, which causes the error.


Log in to reply
 

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