DSA problem
Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. You must not use any built-in BigInteger library or convert the inputs to integer directly.
A naive translation to a built-in integer type fails because either string can be up to two hundred digits long, far exceeding 64-bit. We need to simulate paper-and-pencil multiplication digit by digit, exactly as a child would learn it.
Observation: if num1 has m digits and num2 has n digits, the product has at most m + n digits. Allocate an integer buffer pos of length m + n initialized to zero. For each pair of digits (i, j) — where i indexes from the right of num1 and j from the right of num2 — the product of those two digits contributes to positions (m + n - 1 - (i + j)) (low) and (m + n - 2 - (i + j)) (high) of the buffer. We add the new low digit to the low position, then carry the overflow into the high position.
After all digit-pair contributions are accumulated, walk the buffer from left to right, skipping leading zeros, and convert each integer entry to a character. If the buffer is entirely zero (one of the inputs was zero), return "0". The algorithm runs in O(m * n) time and O(m + n) extra space — the asymptotically optimal complexity for naive multi-digit multiplication.
Examples
num1 = "2", num2 = "3""6"num1 = "123", num2 = "456""56088"num1 = "0", num2 = "999999""0"Constraints
- 1 <= num1.length, num2.length <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.