2 minute read

Multiply 2 integers as arrays - Elements of Programming Interviews (EPI)

Problem:

Write a program that takes 2 arrays that represent integers and returns an array that represents their product. Example :[1,2,1,1] * [1,4,1] should return [1,7,0,7,5,1].

Solution:

We simply try to convert the gradeschool algorithm for multiplication where we multiply each digit of the first number with each digit of the second number and shift over the result by 1 digit and sum all of it together. We had a very poor implementation of this since we implemented a helper method for adding 2 arbitrary sized arrays which was unnecessary. Our solution:

def multiply(num1: List[int], num2: List[int]) -> List[int]:
    """Function to multiply 2 integers represented as arrays"""
    neg = 1
    if num1[0] < 0:
        neg *= -1
        num1[0] *= -1
    if num2[0] < 0:
        neg *= -1
        num2[0] *= -1

    def add(x, y):
        """Function to add 2 integers represented as arrays
        in reversed order. 123 is [3,2,1]"""
        c = 0
        r = []
        leftover = None
        while x and y:
            temp = x.pop(0) + y.pop(0) + c
            c = temp // 10
            r.append(temp % 10)
        if x:
            leftover = x
        elif y:
            leftover = y
        while leftover:
            temp = leftover.pop(0) + c
            c = temp // 10
            r.append(temp % 10)
        if c:
            r.append(1)
        return r

    # print(list(reversed(add([1],[4,5,6]))))
    #smaller, larger = (num2, num1) if len(num1) > len(num2) else (num2, num1)
    smaller = num1 if len(num1) <= len(num2) else num2
    larger = num1 if len(num1) > len(num2) else num2
    result = []
    i = 0
    for n2 in reversed(smaller):
        carry = 0
        tmp2 = []
        for n1 in reversed(larger):
            tmp = n1*n2+carry
            tmp2.append(tmp % 10)
            carry = tmp // 10
        if carry:
            tmp2.append(carry)
        result = add(result, [0]*i + tmp2)
        i += 1

    result[-1] *= neg
    if not any(result):
        result = [0]
    return list(reversed(result))

A cleaner solution from the book does not use any extra adding methods and instead initializes a result array with the max possible size which would be digits of first int + digits of second int. 9999*999 = 7 digits answer. Then simply keep updating elements of that array during the calculation. Rather than first computing a temporary array with the result of one computation and then adding that array to the cumulative result.

def multiply(num1: List[int], num2: List[int]) -> List[int]:

    sign = -1 if (num1[0] < 0) ^ (num2[0] < 0) else 1
    num1[0], num2[0] = abs(num1[0]), abs(num2[0])

    result = [0] * (len(num1) + len(num2))
    for i in reversed(range(len(num1))):
        for j in reversed(range(len(num2))):
            result[i + j + 1] += num1[i] * num2[j]
            result[i + j] += result[i + j + 1] // 10
            result[i + j + 1] %= 10

    # Remove the leading zeroes.
    result = result[next((i for i, x in enumerate(result)
                          if x != 0), len(result)):] or [0]
    return [sign * result[0]] + result[1:]

This is a much better solution which maps a particular location in the result to the indexes i and j in the original arrays.