Call for help to understand "Memory Limited Exceed" error (though code passes test on local IDE)


  • 0

    So Below code works fine on my local IDE, where I also list my unit test results.
    I got MLE error when OJ tests findNthDigit(10000000).
    I originally guess it is because I count too many local vars pos_start and pos_end, so I use a hashmap to store previously calculated results and use them to calculate the new round, but still failed with MLE error.

    I am not from CS background, so I don't understand where my code could have a MLE? and why I could pass local IDE test if there is any error that not accepted by OJ?
    Thanks!

    import math
    class Solution(object):
        def findNthDigit(self, n):
            """
            :type n: int
            :rtype: int
            """
            pos_HashMap = {0:1}
            for e in xrange(1, int(math.log( (2**31 - 1), 10)) + 1): # find which group n is in
                pos_start = pos_HashMap[e-1] + 9 * (int(10 ** ((e-1) - 1)) * (e-1))
                pos_HashMap.update({e: pos_start})
                # pos_start = sum([9 * (10 ** (i - 1) * i) for i in xrange(1, e)]) + 1 # this group's start and end position
                pos_end = pos_start + 9 * (10 ** (e - 1)) * e - 1
                if n in range(pos_start, pos_end + 1): # if n in this position interval
                    num_start = 10 ** (e - 1) # find this group's start value
                    n_val_tgt = (n - pos_start)/e + num_start # find n's real value and return its digit
                    n_val_rm = (n - pos_start)%e
                    return int(str(n_val_tgt)[n_val_rm])
    
    if __name__ == '__main__':
        print Solution().findNthDigit(10000000) # 7
        # print Solution().findNthDigit(3) #3
        # print Solution().findNthDigit(9) #9
        # print Solution().findNthDigit(11) #0
        # print Solution().findNthDigit(28) #1
        # print Solution().findNthDigit(100) #5
    

  • 0

    Make the number larger so that your code crashes on your PC as well, then find out where and why. I think Python will even tell you why (but I can't test it right now).


  • 0

    @StefanPochmann Thanks, Stefan!

    Yes, I have tried Solution().findNthDigit(999999999) in terminal. It runs some time without giving a result and feedback "Killed: 9". In this regard, it is MLE for my local IDE.

    So my question now goes to how come I consume too much memory, I tried to use a Hashmap to record previously result in order to decrease the memory used to calculate an intermediate result. I have no clue where I could enhance the efficiency better.

    I know you have given your solution out, which is great! But for my solution, Any suggestion on improving efficiency?

    Thanks very very much :) !


  • 0

    When I run it (in IDLE's shell), I get this:

    >>> print Solution().findNthDigit(1000000000)
    
    Traceback (most recent call last):
      File "<pyshell#4>", line 1, in <module>
        print Solution().findNthDigit(1000000000)
      File "<pyshell#2>", line 13, in findNthDigit
        if n in range(pos_start, pos_end + 1): # if n in this position interval
    MemoryError
    

    So it does tell me exactly where it happens.

    The problem is that that's a huge range. You're creating a huge list in memory there. For no good reason, even, since you're just using it for the in check.


  • 0

    @StefanPochmann Perfectly explained the problem! Thanks very much!
    I misunderstand your previous suggestion to use IDLE (which actually you meant to use shell IDLE by type "IDLE" as terminal and use the popped out IDLE shell window to track the problem, rather not to use PyCharm which provides an IDLE environment. )

    Yes! IDLE command shell do give me the similar feedback! Got your point! Thanks very much :)


  • 0

    Hmm, I just tried it in PyCharm and get a similar error there as well:

    C:\Python27\python.exe C:/Users/Stefan/PycharmProjects/untitled/test.py
    Traceback (most recent call last):
      File "C:/Users/Stefan/PycharmProjects/untitled/test.py", line 21, in <module>
        print Solution().findNthDigit(100000000) # 7
      File "C:/Users/Stefan/PycharmProjects/untitled/test.py", line 14, in findNthDigit
        if n in range(pos_start, pos_end + 1): # if n in this position interval
    MemoryError
    
    Process finished with exit code 1
    

Log in to reply
 

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