patternpythonMinor
SPOJ ADDREV challenge - Adding reversed numbers
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:
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...
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.