Write a program that takes two arrays representing integers, and returns an integer representing their product.
Solution: we can use the grade-school algorithm for multiplication which consists of multiplying the first number by each digit of the second, and then adding all the resulting terms.
def multiply(num1, num2):
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
# Removing the leading zeros
result = result[next((i for i, x in enumerate(result) if x != 0), len(result)):] or [0]
return [sign * result[0]] + result[1:]
There are m partial products, each with at most n + 1 digits. We perform O(1) operations on each digit in each partial product, so the time complexity is O(nm).
Algorithm Design 