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?

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

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]