Multiply Two Integers

Given two integersnum1andnum2represented as lists, return the product ofnum1andnum2, also represented as a list. num1andnum2maybe negative if the leading digit is negative.

Example 1:

Input: num1 = [2], num2 = [3]
Output: [6]

Example 2:

Input: num1 = [1,2,3], num2 = [-4,5,6]
Output: [-5,6,0,8,8]

Note:

1. Both num1and num2contain only digits0-9.

2. Both num1and num2 do not contain any leading zero, except the number 0 itself.

3. You must not convert the inputs to integer directly.

Solution

Idea:

1. The number of digits required for the product is at most $n + m$ for $n$ and $m$ digit operands. So we can initialize the result as an $m + n$ array for multiplication and remove all leading zeros at the final step.

2. Simulate the integer multiplication algorithm.

Time complexity: $O(mn)$ $O(mn)$, where $m, n$$m, n$ are length of inputs.

def multiply(num1, num2):
    """
    :type num1: list
    :type num2: list
    :rtype: list
    """
    # deal with corner case
    if num1 == [0] or num2 == [0]:
        return [0]

    sign = -1 if num1[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 range(len(num1)-1, -1, -1):
        for j in range(len(num2)-1, -1, -1):
            result[i+j+1] += num1[i] * num2[j]
            result[i+j] += result[i+j+1] // 10
            result[i+j+1] %= 10
    result = result[next(i for i, x in enumerate(result) if x != 0):]
    return [result[0] * sign] + result[1:]