SPOJ ADDREV challenge - Adding reversed numbers

Question

I'm a beginner Python (2.7) programmer, and I've just started solving basic problems on SPOJ. I correctly solved the ADDREV problem (http://www.spoj.com/problems/ADDREV/), however my code takes 0.06s time and 8.8M memory to run. The top Python 2.7 rankers for the problem take <0.005s and 4.00M. Since I am starting out and this is a simple code snippet, I would love to get specific tips on how I can optimise the code below to reach these levels of efficiency. I am reading popularly available tips to optimise Python code, including the use of profilers, however I would really appreciate any tips I can already get here.

The problem as described there:

Input

The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

Output

For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

^{(Source: http://www.spoj.com/problems/ADDREV/)}

Here's the code:

def reverse(num):   # Takes a string as input and reverses it, removing any leading or trailing zeros
    num = num.strip("0")
    return num[::-1]

num_cases = input()

for i in range(0, num_cases):
    usr_input = raw_input()
    arr = usr_input.split()
    reversed_sum = int(reverse(arr[0])) + int(reverse(arr[1]))
    print reverse(str(reversed_sum))

Answer 1

A simple optimization would be to use xrange(..) instead of range(..). range(..) in Python 2.7 loads the entire range into memory. xrange(..) on the other hand has "lazy evaluation", which means that it only calculates the next number in the sequence when it is needed. This reduces the memory footprint.

The other heavy thing you are doing is reversing strings three times, and stripping the strings from 0's each time. If you follow the algorithm completely, I don't think you can do much else. However... let's take a look at some not so random examples:

          1234 + 4123
Reversed: 4321 + 3214
Added:    7535
Reversed: 5357

That's an aweful lot like the result of 1234 + 4123. So what's the difference? Well... if two digits add up to more than 10, this is no longer true. We don't add the carry to the digit to the left, but to the digit to the right.

          1294 + 4123
Reversed: 4921 + 3214
Added:    8135
Reversed: 5318

Guess in which direction we write the output? Well, from left to right. So if we add each pair, we can just add the carry to the next digit we write. There are two more questions we have to answer. The first: What if one of the numbers is smaller? How do we align them?

          12 + 4123
Reversed: 21 + 3214
Added:    3235
Reversed: 5323

From that example we can deduce that REVADD'ing 12 + 4123 is like normal adding of 1200 + 4123. The last question is: What if the length of the result is not equal to the things we add?

          9876 + 7896
Reversed: 6789 + 6987
Added:    13776
Reversed: 67731

That is indeed what we would get if we would do the proposed algorithm. You would end up with something like this:

from __future__ import print_function

zero = ord('0')
doublezero = zero * 2

a, b = usr_input.split()
if len(a) < len(b):
    a, b = b, a

carry = 0

for j in xrange(0, len(b)):
    c = ord(a[j]) + ord(b[j]) - doublezero + carry
    print(chr((c % 10) + zero), sep='', end='')
    carry = c / 10

if carry and len(a) == len(b):
    print('1')
elif carry:
    print(chr(ord(a[j+1])+1), a[j+2:], sep='')
else:
    print(a[j+1:])

Answer 2

The biggest savings comes from computing the results directly from the textual representation of the inputs, instead of converting inputs to numbers, reversing them, adding them, reversing the result and then converting it to text.

Just add the character codes of the inputs to the current carry (initially 0, of course) and deduct the difference between '0' and 0 since the intermediate result contains it twice. If the result is greater than '9', subtract 10 and set the new carry to 1. Rinse and repeat.

P.S.: the task description talks about 'reversed' numbers but one might as well call them 'Little Endian'. That's why one can simply add the digits as they come in and push the result digits out, until the longer of the two inputs ends and the carry is down to 0...