HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

SPOJ ADDREV challenge - Adding reversed numbers

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
challengenumbersreversedspojaddingaddrev

Problem

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 (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))

Solution

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...

Context

StackExchange Code Review Q#134536, answer score: 2

Revisions (0)

No revisions yet.