Вернуть массив СУММ из двух массивов

Question

Меня недавно спросили об этом в моем 1-м интервью по кодированию, и это все еще меня озадачило ...

Задача:

• Вернуть массив, равный сумма двух массивов
• Массивы могут быть пустыми
• Массивы могут быть разных размеров
• Элементы в массиве всегда будут иметь тип (int)
• Вы не можете использовать библиотека или numpy или любые встроенные функции

Пример ввода с ожидаемым выводом:

add_two_array([1, 2, 3], [4, 5, 6]) => [5, 7, 9]

add_two_array([9, 8, 7], [6, 5, 4]) ==> [1, 6, 4, 1]

Answer 1

Я не совсем понимаю требование «не могу использовать никакие встроенные функции». Какой смысл в использовании языка. При этом используется только тип списка для добавления и реверсирования (среза):

def add_two_array(arr1, arr2):
    def arr_to_int(arr):
        n = e = 0
        for d in arr[::-1]:
            n += d*10**e
            e += 1  # would be easier to use enumerate
        return n    # return sum(d*10**e for e, d in enumerate(arr[::-1])

    total = arr_to_int(arr1) + arr_to_int(arr2)
    result = []
    while total:
        result.append(total%10)
        total //= 10
    return result[::-1]

In []:
add_two_array([1, 2, 3], [4, 5, 6])

Out[]:
[5, 7, 9]

In []:
add_two_array([9, 8, 7], [6, 5, 4])

Out[]:
[1, 6, 4, 1]

Альтернативным (немного более уродливым) способом было бы использование обратного индекса и перенос остатка. Использует троичный оператор для установки значения по умолчанию 0:

def add_two_array(arr1, arr2):
    result = []
    rem = 0
    for i in range(max(len(arr1), len(arr2))-1, -1, -1):
        n = (arr1[i] if i < len(arr1) else 0) + (arr2[i] if i < len(arr2) else 0) + rem
        result.append(n%10)
        rem = n//10
    if rem:
        result.append(rem)
    return result[::-1]

In []:
add_two_array([9, 8, 7], [6, 5, 4])

Out[]:
[1, 6, 4, 1]

Answer 2

в вашем заявлении о проблеме отсутствует признак того, что вы действительно хотите добавить цифры и перенести дополнительные десять:

def add_two_array(A,B,carry=0):
    if not (A or B or carry): return []
    carry += A[-1] if A else 0
    carry += B[-1] if B else 0
    return add_two_array(A[:-1],B[:-1],carry//10)+[carry%10]


r = add_two_array([1, 2, 3], [4, 5, 6]);
print(r) # [5, 7, 9]
r = add_two_array([9, 8, 7], [6, 5, 4]);
print(r) # [1, 6, 4, 1]

Answer 3

Это крутая проблема и может быть рекурсивно решена без использования каких-либо встроенных функций и методов. Здесь _add2 и _add3 - рекурсивные вспомогательные функции, а add - оболочка.

def _add2(a, carry):
    if a == []: return [carry] if carry else []
    s = a[-1] + carry
    digit = s % 10
    carry = s // 10
    return _add2(a[:-1], carry) + [digit]

def _add3(a, b, carry):
    if a == []: return _add2(b, carry)
    if b == []: return _add2(a, carry)
    s = a[-1] + b[-1] + carry
    digit = s % 10
    carry = s // 10
    return _add3(a[:-1], b[:-1], carry) + [digit]

def add(a, b):
    return _add3(a, b, 0)

add([9, 8, 7], [1, 6, 5, 4])
#[2, 6, 4, 1]
add([1, 6, 5, 4], [9, 8, 7])
#[2, 6, 4, 1]