how do I prevent memory error for the following code

Question

This my python code it's working fine for small values as in primary testcases, but producing Memory Error due to large integer values. How can remove the Memory Error or how do I perform operations with large integers in python please?

#taking input testcases T
n=int(raw_input())

#taking value range upto iterate and find reversible numbers
_input_var = [int(raw_input()) for i in range(0,n)]


#function will reverse the number and return
def reverse(num):
    return int(str(num)[::-1])

#function will check odd confirmation for every digit 
def isDigitOdd(num):
    lista = str(num)
    for i in lista:
        if int(i)%2==0:
            flag = False
            return flag
        else:
            flag = True
    return flag

#main method
def main(_iter):    
    count=0
    for i in range(0,_iter):
        k = i + reverse(i)
        if i%10!=0 and isDigitOdd(k):
            count+=1
    print count

#calling main method for N number ranges
for i in _input_var:
    main(i)

Please be more specific. Exactly which value of n gives you an error? Show the entire callback. — Rory Daulton
– Rory Daulton, Commented Jun 23, 2016 at 16:19
@RISHABMITTAL timeouts have nothing to do with memory issues. Did xrange solve the Memory Error issue? If yes, than your question is answered. Improving speed is a different question that is related to your algorithm and optimisations. — Eli Korvigo
– Eli Korvigo, Commented Jun 23, 2016 at 16:27
@RISHABMITTAL - Suppose it takes only a nanosecond for each cycle through the main loop. That means it will take 10^9 seconds (almost 32 years) to finish in the case of 10^18. Note that there is no way the test computer will calculate n+reverse(n) in a nanosecond, let alone checking whether each digit in the sum is odd. A brute force solution will take several centuries to arrive at an answer. You cannot use brute force to solve this problem. — David Hammen
– David Hammen, Commented Jun 23, 2016 at 18:15

Eli Korvigo · Accepted Answer · 2016-06-23 23:27:57Z

2

Most likely, you run out of memory when a big number is passed to range, because it has to build the entire list in memory. Replace range calls with xrange.

def main(_iter):    
    count=0
    for i in xrange(0,_iter):
        k = i + reverse(i)
        if i%10!=0 and isDigitOdd(k):
            count+=1
    print count

xrange is a lazy generator that, similarly to range in Python 3, has O(1) memory complexity. xrange uses a 64-bit C long int on 64-bit platforms to store internal state, that is the limit is almost ±10^19 (it throws OverflowError if a number exceeds that limit). Anyway, as I've already mentioned in the comments (along with other users) your algorithm is too naïve to handle a big input. You must reduce the asymptotic complexity. Something like O(log(n)) should do just fine.

P.S. Some minor optimisations

def isDigitOdd(num):
    return all(int(digit) % 2 for digit in str(num))

def main(_iter):    
    print(sum(i % 10 and isDigitOdd(i+reverse(i)) for i in xrange(0,_iter)))

edited Jun 23, 2016 at 23:27

answered Jun 23, 2016 at 16:19

Eli Korvigo

10.5k6 gold badges50 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

bhansa Over a year ago

your code is returning 0 0 value on providing 2 1000 948 as input.

Eli Korvigo Over a year ago

@Bhansa fixed that

Brendan Abel · Accepted Answer · 2016-06-23 16:18:54Z

0

It's likely this line

for i in range(0,_iter)

This will create a list of length _iter, which will be massive for large values. You actually don't need to store the whole list; you only need to increment a single integer. Instead, use xrange, which produces a generator that will only create and store one integer at a time:

for i in xrange(0,_iter)

answered Jun 23, 2016 at 16:18

Brendan Abel

38k16 gold badges101 silver badges126 bronze badges

Collectives™ on Stack Overflow

how do I prevent memory error for the following code

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related