Sum numbers digit by digit

Question

The problem goes like this:

Given two one-dimensional arrays, for example a = (3, 4, 5) and b = (5, 6, 9), write a function that sums the arrays as a number digit by digit, i.e. producing c = (9, 1, 4). Do not use any high-level functions such as str.join() or str.split().

345 +
569
---
914

My solution:

def sum_arr(arr1, arr2):
 
 l = max(len(arr1), len(arr2))
 
 if len(arr1) < l:
 arr1 = (0,)*(l - len(arr1)) + arr1
 
 if len(arr2) < l:
 arr2 = (0,)*(l - len(arr2)) + arr2
 
 result = [0]*l
 carry = 0
 
 for idx in range(l - 1, -1, -1): 
 val = arr1[idx] + arr2[idx] + carry
 
 if val < 10:
 result[idx] += val
 carry = 0
 else:
 result[idx] += val % 10
 carry = 1
 
 if carry:
 result = [1] + result
 
 
 return tuple(result)

Is there any more concise/elegant solution?

• Peter Cordes: FYI, most BigInteger libraries (and CPython internally) use a "little-endian" storage format, so the least-significant chunk is at the lowest address, opposite of this tuple order your assignment annoyingly requires. Little-endian means a[i] and b[i] have the same place value. BigInteger software normally uses base 2^32 or 2^64 chunks, or 2^30 to allow software carry propagation like CPython internals. Working on one decimal digit per add operation is really inefficient, but good for understanding the concept of carry propagation.

Answer 1

Types

When I hear one-dimensional array, I think first think of a list [3, 4, 5], not a tuple (3, 4, 5). If your method is given two lists of unequal length, one of the if statements will fail with the exception:

TypeError: can only concatenate tuple (not "list") to tuple

You could avoid this by converting the input type to a tuple: eg)

 arr1 = (0,) * (digits - len(arr1)) + tuple(arr1)

Variable names

l is a terrible variable name. It looks too close to 1. digits or num_digits would be much clearer.

Loop like a Native

See talk by Ned Batchelder.

Python is a scripted language. As a consequence of this, there are common coding patterns that have inefficiencies. Looping over the indices of a container is probably the most common one. It looks like:

 for idx in range(len(container)):
 # code which never uses idx except as container[idx]

Instead, the code should loop over the values in the container:

 for value in container:
 # code which uses value

In your case, you want to loop over two containers simultaneously, so what is done is the containers are zipped together (note: like a zipper, not file compression):

 for value1, value2 in zip(container1, container2):
 # code which uses value1 & value2

Again in your case, we need to start at the end of the arrays and work backwards. Python provides a "reverse iterator" which will start at the end and move towards the start:

 for digit1, digit2 in zip(reversed(arr1), reversed(arr2)):
 val = digit1 + digit2 + carry
 ...

You preprocessed the inputs to ensure they were the same length. That is not necessary. zip(...) stops at the end of the shorter input stream, but zip_longest(...) won't stop until all input streams have been exhausted. We can provide a fillvalue= argument to pretend the shorter sequence has zeros at the beginning:

from itertools import zip_longest
...
 for digit1, digit2 in zip_longest(reversed(arr1), reversed(arr2),
 fillvalue=0):
 val = digit1 + digit2 + carry
 ...

divmod

Python provides a divmod function, which both integer-divides a value by some divisor and computes the modulus after division. Using divmod(val, 10) would directly give you the carry and remainder.

 carry, digit_sum = divmod(digit1 + digit2 + carry, 10)

Reworked code

The following uses the above changes, plus adds type-hints for the arguments and return value, and a docstring for the whole function. Embedded in the docstring are two "doctest" examples, which is exercised by the doctest.testmod() in the main-guard.

from itertools import zip_longest
from typing import Sequence
def sum_digit_by_digit(arr1: Sequence[int], arr2: Sequence[int]) -> list[int]:
 """
 Add two non-negative integers given as two one-dimensional arrays of
 digits, most-significant digit first.
 >>> sum_digit_by_digit([3, 4, 5], [5, 6, 9])
 [9, 1, 4]
 >>> sum_digit_by_digit((3, 4, 5), (6, 7, 9))
 [1, 0, 2, 4]
 """
 result = []
 carry = 0
 for digit_1, digit_2 in zip_longest(reversed(arr1), reversed(arr2),
 fillvalue=0):
 carry, digit_sum = divmod(digit_1 + digit_2 + carry, 10)
 result.insert(0, digit_sum)
 if carry:
 result.insert(0, carry)
 return result
if __name__ == '__main__':
 import doctest
 doctest.testmod()

As demonstrated in the doctests, the input to the function may be given as either lists or tuples.

Update

As noted by @Eugene Yarmash, the insert(0, ...) in the loop is an \$O(N^2)\$ operation, and this would slow down as the number of digits increases. We can use .append(), and reverse the result at the end.

from itertools import zip_longest
from typing import Sequence
def sum_digit_by_digit(arr1: Sequence[int], arr2: Sequence[int]) -> list[int]:
 """
 Add two non-negative integers given as two one-dimensional arrays of
 digits, most-significant digit first.
 >>> sum_digit_by_digit([3, 4, 5], [5, 6, 9])
 [9, 1, 4]
 >>> sum_digit_by_digit((3, 4, 5), (6, 7, 9))
 [1, 0, 2, 4]
 """
 result = []
 carry = 0
 for digit_1, digit_2 in zip_longest(reversed(arr1), reversed(arr2),
 fillvalue=0):
 carry, digit_sum = divmod(digit_1 + digit_2 + carry, 10)
 result.append(digit_sum)
 if carry:
 result.append(carry)
 return result[::-1]
if __name__ == '__main__':
 import doctest
 doctest.testmod()

• Eugene Yarmash: This is really good stuff! I would just avoid using list.insert(0, val) in a loop as it's O(n^2).
• AJNeufeld: @EugeneYarmash That is a fair point. I was avoiding enumerate() to keep the for ... zip() from getting too complicated, but perhaps .append() and returning the reversed result would be a good alternative.
• Reinderien: @EugeneYarmash the amortized worst-case list insert is not O(n^2)
• Reinderien: Unless you mean to include the outer loop that calls it, in which case yeah you're right.
• Peter Cordes: digits isn't a great name either; from the name alone you might guess it's a list that holds the digits. So yeah, num_digits, or len, or if someone insists on one-letter var names that are hard to search on, n.

Answer 2

The op's question suggests a method to sum to numbers given as two arrays of digits. However, the code appears a little bit longish on the first glance (e.g. the carry is assigned using an if-clause instead of a calculation). Also the modification of the original arrays is probably not intended as it may give false promises to the caller of the sum_arr function. Then if len(arr) < 1 -> len(arr) == 0. Thereford I don't understand why len(arr) is used again in the body of the if. The variable naming could be improved.

In my solution I tried to tackle those critic points. I also avoided the reverse() method like in the op to NOT change the original lists. Indexing is therefore to be preferred in my opinion. Remember, lists are passed by reference. I also added checks that single digit is <10. Use assertion or conditional dependent on the context. Furthermore the code assumes that the shorter list is prefixed by 0's up the the size of the larger list.

Here is my code:

import contextlib
def sum_array_as_number(arr1, arr2):
 carry = 0
 max_len = max(len(arr1), len(arr2))
 res = [0] * max_len
 for i in range(-1, -max_len - 1, -1):
 val1 = val2 = 0
 with contextlib.suppress(IndexError):
 val1 = arr1[i]
 val2 = arr2[i]
 assert val1 < 10, "Digit must be < 10"
 assert val2 < 10, "Digit must be < 10"
 carry, digit = divmod(val1 + val2 + carry, 10)
 res[i] = digit
 return res

Example:

res_arr = sum_array_as_number([1, 3, 4, 5], [5, 6, 9])
print(res_arr)

->

[1, 9, 1, 4]

• AJNeufeld: The OP’s code is not testing if len(arr) < 1 (one), rather it is testing if len(arr) < l(lowercase-L).
• AJNeufeld: The caller’s arrays are not being modified. arr1 = ... is assigning a new value to the local variable, and does not affect the original arrays of the caller.
• AJNeufeld: reversed(...) is an \$O(1)\$ function which does not modify the original object or create a copy of the original object. It creates an iterator that will return successive elements starting from the end and working backwards.
• Eugene Yarmash: The function returns a different result if you swap the arguments (i.e. call it like sum_array_as_number([5, 6, 9], [1, 3, 4, 5])).
• Looser User: Ah my fault. It would need two suppressions, each for val1 and val2. I think I'll rework the code using two loops, one for 0..min_len and one for min_len..max_len. Conditionals inside loop are performance killers.