Start learning free

LESSON 599 OF 673 · MATH

Multiply Strings in Python: O(m · n) Digit-by-Digit Method

Practice O(m · n) Read the full explanation

You get two strings, num1 and num2. Each one holds a whole number written in digits.

Return the product of the two numbers, also as a string. It has no zeros in front, so a product of 0 is "0".

A number can have up to 1,000 digits. Numbers that long don't fit in the usual integer types. So don't turn a whole string into a number. Work with its digits instead.

 

Example 1:

Input: num1 = "25", num2 = "16"
Output: "400"
Explanation: 25 times 16 is 400.

Example 2:

Input: num1 = "999", num2 = "99"
Output: "98901"
Explanation: 999 times 99 is 98901.
The answer has 5 digits, as many as both numbers together.

Example 3:

Input: num1 = "0", num2 = "8317"
Output: "0"
Explanation: Any number times 0 is 0.
The answer is "0", with no extra zeros.

 

Constraints:

  • num1 and num2 each have 1 to 1,000 digits.
  • They hold only the digits 0 to 9.
  • Neither starts with 0, unless it is the number 0.
Note:

Your solution should run in O(m · n) time. Here m and n are the lengths of num1 and num2.



Multiply the way you learned at school. Each digit of num1 meets each digit of num2 once. Two digits make at most 81.

Number the positions of the answer from the left, starting at 0. With m and n digits, there are m + n positions. The product of digit i of num1 and digit j of num2 lands at position i + j + 1. Its tens carry into position i + j.

Every pair of digits takes one step: O(m · n) time.
The answer has at most m + n digits, so the extra space is O(m + n).
STEP 1 OF 12
    Ctrl + Enter to check

    PYTHON · MATH

    Multiply Strings in Python, explained

    Problem overview

    The method multiply gets two non-negative whole numbers as strings, num1 and num2, each with up to 1,000 digits. It returns their product, also as a string, with no zeros in front. A product of 0 is "0". The statement asks you to work with the digits rather than convert a whole string to a number, and to run in O(m · n) time, where m and n are the lengths of the strings.

    For "25" and "16" the answer is "400". For "999" and "99" it is "98901", which has 5 digits, as many as the two inputs together. For "0" and "8317" it is "0".

    Approach: long multiplication on paper

    School multiplication pairs every digit of one number with every digit of the other, and each pair contributes to a column of the answer. Two digits multiply to at most 81. A product with m and n digits has at most m + n digits (99 times 99 is 9801), so a list of m + n zeros can hold the whole answer.

    Number the answer's positions from the left, starting at 0. The digits num1[i] and num2[j] have place values that add up, and their product lands at position i + j + 1, with its tens carried into position i + j. For 25 times 16 the last digits are at i = 1 and j = 1, and 5 times 6 is 30, so the 0 stays in position 3 (the ones) and the 3 carries into position 2 (the tens).

    Going through the pairs from the last digits to the first, as on paper, gives this state of the list after each pair, for "25" times "16":

    i=1 j=1: product 30  [0, 0, 3, 0]
    i=1 j=0: product 5   [0, 0, 8, 0]
    i=0 j=1: product 12  [0, 2, 0, 0]
    i=0 j=0: product 2   [0, 4, 0, 0]

    The list ends as [0, 4, 0, 0]. The leading 0 is skipped, and the answer is "400".

    Step by step

    1. Store the lengths with m, n = len(num1), len(num2). Python assigns the values on the right to the names on the left in order.
    2. Create digits as [0] * (m + n). digits[k] holds the answer's digit at position k from the left. Some leading positions may stay 0.
    3. Loop over num1 from the last digit to the first with range(m - 1, -1, -1). The stop value is left out of a range, so -1 includes index 0.
    4. Loop over num2 the same way with j. Together, the loops pair each digit of one number with each digit of the other: m · n pairs.
    5. Multiply the two digits with int(num1[i]) * int(num2[j]). Only one character is converted at a time; the strings stay strings.
    6. Add the product to what is at position i + j + 1 in total. This is the key line. Earlier pairs may have left a carry or a partial sum there.
    7. Keep the ones digit of total in that position: total % 10.
    8. Carry the rest left by adding total // 10 to digits[i + j]. That position can briefly pass 9. A later pair uses it as its own i + j + 1 spot, adds to it and splits it again.
    9. Skip the leading zeros. After the loops, start begins at 0.
    10. Advance start while start < m + n - 1 and digits[start] is 0. The loop stops before the last position, so a product of 0 keeps one digit.
    11. Add 1 to start in the loop body.
    12. Join the rest into a string with "".join(str(d) for d in digits[start:]).

    The solution in Python

    class Solution:
        def multiply(self, num1: str, num2: str) -> str:
            m, n = len(num1), len(num2)
            digits = [0] * (m + n)
            for i in range(m - 1, -1, -1):
                for j in range(n - 1, -1, -1):
                    product = int(num1[i]) * int(num2[j])
                    total = product + digits[i + j + 1]
                    digits[i + j + 1] = total % 10
                    digits[i + j] += total // 10
            start = 0
            while start < m + n - 1 and digits[start] == 0:
                start += 1
            return "".join(str(d) for d in digits[start:])
    

    Python details:

    • int(num1[i]) turns a single character such as '7' into the number 7. The string is never converted as a whole, which is the point of the lesson. Python's own integers could multiply two 1,000-digit numbers, but this exercise practises the digit method.
    • % and // give the ones digit and the carry of a non-negative total.
    • digits[start:] is a slice, a new list from start to the end. The generator expression str(d) for d in ... turns each digit into text, and "".join glues the pieces with nothing in between.
    • Strings are immutable in Python, so the answer is built in a list of ints and joined once at the end, not by repeated string concatenation.

    Complexity

    Every pair of digits takes a constant number of steps, so the time is O(m · n). The skipping loop and the join add O(m + n). The list holds at most m + n digits, so the extra space is O(m + n).

    Edge cases and common mistakes

    • A zero factor. "0" times "8317" leaves the list all zeros, and the skipping loop stops at the last position, giving "0". With a condition of start < m + n instead, the loop would run off the end and the slice would be empty.
    • Leading zeros. Powers of ten such as "100" times "100" give "10000". The list's first position can be 0 even for a non-zero answer, so it is skipped.
    • Wrong position. Using i + j for the product and i + j + 1 for the carry puts the digits in the wrong columns. The ones digit goes to the right, at i + j + 1.
    • Forgetting the existing value. Setting digits[i + j + 1] = product % 10 instead of adding the earlier content throws away the results of previous pairs.
    • Maximum size. "9" repeated 1,000 times, times itself, gives a 2,000-digit answer, which fits in the m + n positions.

    Testing

    num1num2result
    "25""16""400"
    "999""99""98901"
    "0""8317""0"
    "9""9""81"
    "100""100""10000"
    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free