Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
A complete visual walkthrough of grade-school multiplication using positional digit mapping.
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
1 <= num1.length, num2.length <= 200num1 and num2 consist of digits only.num1 and num2 do not contain any leading zero, except the number 0 itself.The most obvious approach is to convert both strings to integers, multiply them, and convert back. But this fails for a critical reason:
The input strings can have up to 200 digits. Consider what happens:
Even BigInteger is explicitly forbidden. We need to simulate multiplication digit by digit, exactly like you learned in school.
Key realization: We don't need the full number. We just need to process each pair of digits and accumulate their contributions at the correct positions in the result.
When you multiply digit num1[i] by digit num2[j], the product always lands at specific positions in the result:
For digits at indices i and j (0-indexed from left), their product contributes to positions i+j (carry/tens) and i+j+1 (ones) in the result array.
Why does i+j work? Digit at index i from left in num1 represents 10^(m-1-i). Digit at index j represents 10^(n-1-j). Their product has magnitude 10^(m+n-2-i-j), which maps to position i+j (counting from the left of a result array of length m+n).
Let's trace through "123" x "456" step by step, filling the result array of size m + n = 6.
Each cell shows num1[i] x num2[j] and where the product goes in the result array pos[0..5]:
| 4 (j=0) | 5 (j=1) | 6 (j=2) | |
|---|---|---|---|
| 1 (i=0) | 4 p0,p1 |
5 p1,p2 |
6 p2,p3 |
| 2 (i=1) | 8 p1,p2 |
10 p2,p3 |
12 p3,p4 |
| 3 (i=2) | 12 p2,p3 |
15 p3,p4 |
18 p4,p5 |
We process from bottom-right (i=2, j=2) to top-left (i=0, j=0), adding each product into the result positions and carrying over as we go.
After processing all digit pairs (right-to-left), the pos array holds the final digits:
sb.length() == 0 ? "0" : sb.toString() handles this.class Solution { public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] pos = new int[m + n]; // result digits; max length is m+n // Process each digit pair, right to left for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { // Multiply single digits int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); // Target positions in result int p1 = i + j, p2 = i + j + 1; // Add to existing value (handles carry accumulation) int sum = mul + pos[p2]; pos[p2] = sum % 10; // ones digit stays at p2 pos[p1] += sum / 10; // carry goes to p1 } } // Build result string, skipping leading zeros StringBuilder sb = new StringBuilder(); for (int p : pos) if (!(sb.length() == 0 && p == 0)) sb.append(p); return sb.length() == 0 ? "0" : sb.toString(); } }
func multiply(num1 string, num2 string) string { m, n := len(num1), len(num2) pos := make([]int, m+n) // result digits; max length is m+n // Process each digit pair, right to left for i := m - 1; i >= 0; i-- { for j := n - 1; j >= 0; j-- { // Multiply single digits mul := int(num1[i]-'0') * int(num2[j]-'0') // Target positions in result p1, p2 := i+j, i+j+1 // Add to existing value (handles carry accumulation) sum := mul + pos[p2] pos[p2] = sum % 10 // ones digit stays at p2 pos[p1] += sum / 10 // carry goes to p1 } } // Build result string, skipping leading zeros result := "" for _, d := range pos { if result == "" && d == 0 { continue } result += string(rune('0'+d)) } if result == "" { return "0" } return result }
def multiply(num1: str, num2: str) -> str: m, n = len(num1), len(num2) pos = [0] * (m + n) # result digits; max length is m+n # Process each digit pair, right to left for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): # Multiply single digits mul = int(num1[i]) * int(num2[j]) # Target positions in result p1, p2 = i + j, i + j + 1 # Add to existing value (handles carry accumulation) total = mul + pos[p2] pos[p2] = total % 10 # ones digit stays at p2 pos[p1] += total // 10 # carry goes to p1 # Build result string, skipping leading zeros result = "".join(str(d) for d in pos).lstrip("0") return result or "0"
impl Solution { pub fn multiply(num1: String, num2: String) -> String { let b1 = num1.as_bytes(); let b2 = num2.as_bytes(); let (m, n) = (b1.len(), b2.len()); let mut pos = vec![0i32; m + n]; // result digits; max length is m+n // Process each digit pair, right to left for i in (0..m).rev() { for j in (0..n).rev() { // Multiply single digits let mul = ((b1[i] - b'0') * (b2[j] - b'0')) as i32; // Target positions in result let (p1, p2) = (i + j, i + j + 1); // Add to existing value (handles carry accumulation) let sum = mul + pos[p2]; pos[p2] = sum % 10; // ones digit stays at p2 pos[p1] += sum / 10; // carry goes to p1 } } // Build result string, skipping leading zeros let result: String = pos.iter() .skip_while(|&&d| d == 0) .map(|d| ('0' as u8 + *d as u8) as char) .collect(); if result.is_empty() { String::from("0") } else { result } } }
function multiply(num1: string, num2: string): string { const m = num1.length, n = num2.length; const pos: number[] = new Array(m + n).fill(0); // result digits // Process each digit pair, right to left for (let i = m - 1; i >= 0; i--) { for (let j = n - 1; j >= 0; j--) { // Multiply single digits const mul = Number(num1[i]) * Number(num2[j]); // Target positions in result const p1 = i + j, p2 = i + j + 1; // Add to existing value (handles carry accumulation) const sum = mul + pos[p2]; pos[p2] = sum % 10; // ones digit stays at p2 pos[p1] += Math.floor(sum / 10); // carry goes to p1 } } // Build result string, skipping leading zeros const result = pos.join("").replace(/^0+/, ""); return result || "0"; }
Enter two number strings and step through the grade-school multiplication grid cell by cell.
We multiply every digit of num1 (length n) with every digit of num2 (length m), performing O(1) work per pair. The result is stored in an array of length n + m, because the product of an n-digit and m-digit number has at most n + m digits.
Two nested loops iterate every digit of num1 (length n) against every digit of num2 (length m), performing one single-digit multiplication per pair. The result array has at most n + m positions, so space is O(n + m). Grade-school multiplication is inherently O(n × m).
Same nested-loop structure, but the position-mapping trick (i+j, i+j+1) accumulates carries in place, avoiding intermediate string conversions. Every digit pair must be examined, so O(n × m) is a lower bound. The result array of size n + m is the only extra allocation.
The product of an n-digit and m-digit number has at most n + m digits -- pre-allocate the result array to that size. Grade-school multiplication must examine every digit pair, so O(n × m) is inherent. Faster algorithms like Karatsuba (O(n1.585)) exist but are overkill for this problem's constraints.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.