Medium Grade School Multiply Math & Geometry
In plain English: Multiply two large numbers given as strings without using built-in big integer conversion.
Simulate grade-school multiplication. The product of digit at position i and j lands at position i+j and i+j+1 in the result array. Process carries from right to left.
Prompt
Given two non-negative integers represented as strings, return their product as a string. You must not convert the inputs to integers directly.
Try to write it from scratch before scrolling down.
Solution
def multiply(num1, num2):
if num1 == '0' or num2 == '0':
return '0'
n1, n2 = len(num1), len(num2)
result = [0] * (n1 + n2)
for i in range(n1 - 1, -1, -1):
for j in range(n2 - 1, -1, -1):
mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
# p1, p2 map digit positions i,j to their place in the product array
p1, p2 = i + j, i + j + 1
total = mul + result[p2] # add existing value (carry from a previous digit pair)
result[p2] = total % 10
result[p1] += total // 10 # propagate carry leftward
# skip leading zeros
start = 0
while start < len(result) - 1 and result[start] == 0:
start += 1
return ''.join(str(d) for d in result[start:])
# Test: multiply("123", "456") == "56088"
# Test: multiply("2", "3") == "6"
# Test: multiply("0", "12345") == "0"