I'm trying to solve this exercise from Codewars.
Description:
Given the string representations of two integers, return the string representation of the sum of those integers. For example: sumStrings('1','2') // => '3' A string representation of an integer will contain no characters besides the ten numerals "0" to "9". I have removed the use of BigInteger and BigDecimal in java Python: your solution need to work with huge numbers (about a milion digits), converting to int will not work.
In Python, all my test cases are OK, but the Execution Timed Out is still showing up. Any hints to make it work, please? What other approach could i adopt? My current code is down below. Really appreciate any help!!
def sum_strings(x, y):
if x == '' and y == '':
return '0'
if x == '0' and y == '0':
return '0'
if x == '' and y == '0' or x == '0' and y == '':
return '0'
listaX = list(x)
listaY = list(y)
if len(listaX) - len(listaY) > 0:
while len(listaY) < len(listaX):
listaY.insert(0, '0')
if len(listaY) - len(listaX) > 0:
while len(listaY) > len(listaX):
listaX.insert(0, '0')
for i in range(0, len(listaX)):
listaX[i] = int(listaX[i])
listaY[i] = int(listaY[i])
listaSomas = []
quociente = 0
for i in range(len(listaX) - 1, -1, -1):
soma = listaX[i] listaY[i] quociente
if soma > 9 and i > 0:
quociente = soma // 10
listaSomas.insert(0, soma % 10)
elif soma > 9 and i == 0:
quociente = soma // 10
listaSomas.insert(0, soma % 10)
listaSomas.insert(0, quociente)
elif soma <= 9:
listaSomas.insert(0, soma)
quociente = 0
if listaSomas[0] == 0:
listaSomas.remove(listaSomas[0])
for i in range(0, len(listaSomas)):
listaSomas[i] = str(listaSomas[i])
listaSomas = ''.join(listaSomas)
return listaSomas
#MAIN
print(sum_strings('123', '456'))
CodePudding user response：
I had a go, I'm not sure if the kata interface is functioning correctly. As the (below) code tests fine, and does indeed return before 12seconds (12,000 milliseconds)
def clean_int(v):
if len(v) == 0:
return 0
return int(v)
def sum_strings(x, y):
ci = clean_int
return f'{ci(x) ci(y)}'
This is fast enough as I can run this more than 800k well before 12 seconds. - the kata app seems to be malfunctioning unless there's some obscure speed up they're expecting.
CodePudding user response：
One loop should be enough, in order to sum up each digit of both numbers:
def sum_strings(x, y):
# remove whitespaces from x and y
x,y = map(str.strip, (x,y))
# skip useless inputs
if (x == '0' and y =='0') or (x == '' and y == ''):
return "0"
# determine max string, so we could fill the smaller one with leading 0s
maxLen = max(len(x), len(y))
# pad both numbers with 0s and reverse them, so we can sum the digits up
x = x.zfill(maxLen)[::-1]
y = y.zfill(maxLen)[::-1]
r = []
carryover = 0
# sum both digits and keep the carryover!
for i in range(maxLen):
carryover, res = str(int(x[i]) int(y[i]) int(carryover)).zfill(2)
r.append(res)
# add the carryover for the last digit as is!
if i == maxLen-1:
r.append(carryover)
r = "".join(r)[::-1].lstrip("0")
return r if r else "0"
Out:
print(sum_strings('19', '12'))
>> 31
CodePudding user response：
Your code times out because list.insert(0... is slow. When you insert at the beginning, all the other elements need to be move up one index.
Use .append(...) instead, and reverse the list when you're done.
CodePudding user response：
I saw that link and it clearly says : Python: your solution need to work with huge numbers (about a milion digits), converting to int will not work.
Some improvements I can think of are:
a) Don't insert and remove for each digit. Just append to an resultant list.
b) You don't need to append 0s before processing your strings.
A quick way to code it correctly and this got accepted:
def sumdigits(c, a=0, b=0):
s = a b c
if s >= 10:
c = s // 10
s = s % 10
else:
c = 0
return s, c
def sum_strings(x, y):
i = len(x)
j = len(y)
c = 0
out = []
while i > 0 and j > 0:
s, c = sumdigits(c, int(x[i-1]), int(y[j-1]))
out.append(s)
i -= 1
j -= 1
while i > 0:
s, c = sumdigits(c, int(x[i-1]))
out.append(s)
i -= 1
while j > 0:
s, c = sumdigits(c, int(y[j-1]))
out.append(s)
j -= 1
if c > 0:
out.append(c)
out = ''.join([str(n) for n in reversed(out)]).lstrip("0")
if out:
return out
return "0"
CodePudding user response：
Your code times out because of expensive operations, as I mentioned in my original comment. The main problem is inserting at the start of a list. Look up insert vs append for strings and lists here:
https://wiki.python.org/moin/TimeComplexity
As you can see here, appending to a list or string is O(1) but inserting is O(n) because you have to move the rest of the list around. You do this for every digit, so you have O(n^2) complexity just to store the output.
Instead of the expensive insert-at-front operation, store the results with the much more efficient append operation. Once that's all done, simply reverse the output. String and list support efficient reversal.
What is the time complexity of Python List Reverse?
Since we want to iterate, it makes no sense to write your loops with extra code to pad the lengths. It's already done for you in itertools.
I additionally perform my digit math with ord and chr, although that's a relatively minor time saver.
from itertools import zip_longest
zero = ord('0')
nine = ord('9')
def sum_digits(x, y, carry):
answer = ord(x) ord(y) - zero
if carry:
answer = 1
carry = False
if answer > nine:
carry = True
answer = answer - 10
return chr(answer), carry
def sum_strings(x, y):
answer = ''
carry = False
for a, b in zip_longest(reversed(x), reversed(y), fillvalue='0'):
c, carry = sum_digits(a, b, carry)
answer = c
if carry:
answer = '1'
answer = answer.rstrip('0')
if not answer:
return '0'
return ''.join(reversed(answer))