Multiply Two Numbers Represented as Strings
Solve this Problem
Given two non-negative integers
num1 and num2 represented as strings, return their product as a string — without ever converting the inputs to native integers, since they may be arbitrarily large.
The naive approach mirrors long multiplication exactly: multiply num1 by each digit of num2 in turn, shift each partial product into place with trailing zeros, and add everything together with repeated string addition. It works, but every digit triggers a fresh full-length addition. The position arrayPosition ArrayA single array sized to hold every possible digit of the final product, where each pair of input digits is accumulated directly into its known destination positions — no intermediate partial-product strings ever need to be built. technique skips that: since multiplying the digit at position i by the digit at position j always lands at result positions i+j and i+j+1, every digit pair can be accumulated directly into one shared array in a single pass.
Test Case 1:
Input:num1 = "123", num2 = "9"
Output:"1107"
Explanation:123 × 9 = 1107, computed digit by digit without ever forming a native integer.
Test Case 2:
Input:num1 = "2", num2 = "3"
Output:"6"
Explanation:The smallest possible case — a single digit times a single digit.
Test Case 3:
Input:num1 = "0", num2 = "12345"
Output:"0"
Explanation:Anything times "0" is "0", regardless of how large the other number is.
Constraints
- ◆
1 ≤ num1.length, num2.length ≤ 200 - ◆
num1 and num2 consist of digits only - ◆
Neither num1 nor num2 has a leading zero, except the number "0" itself - ◆
You may NOT convert the inputs directly to native integers and multiply — they may be arbitrarily large, larger than any fixed-width integer type
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public String multiplyStrings(String num1, String num2) { |
| 3 | if (num1.equals("0") || num2.equals("0")) return "0"; |
| 4 | int m = num1.length(), n = num2.length(); |
| 5 | int[] result = new int[m + n]; |
| 6 | for (int i = m - 1; i >= 0; i--) { |
| 7 | for (int j = n - 1; j >= 0; j--) { |
| 8 | int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); |
| 9 | int sum = mul + result[i + j + 1]; |
| 10 | result[i + j + 1] = sum % 10; |
| 11 | result[i + j] += sum / 10; |
| 12 | } |
| 13 | } |
| 14 | StringBuilder sb = new StringBuilder(); |
| 15 | for (int num : result) { |
| 16 | if (!(sb.length() == 0 && num == 0)) sb.append(num); |
| 17 | } |
| 18 | return sb.toString(); |
| 19 | } |
| 20 | } |
| 21 |
String
1
2
3
String
9
Array
0
0
0
0
0
1
2
3
Variables
m
3n
1INITIALIZE
Neither num1 nor num2 is "0". Allocate a position array of size m+n = 3+1 = 4, all zeros — every digit pair's product lands in exactly two of these positions.
Step 1 / 6
Approach & Solutions
Brute Force — Multiply by Each Digit, Then Add Partial Products
BruteThis is exactly the long multiplication taught in school: for each digit of num2 (right to left), multiply the ENTIRE num1 by that one digit to get a partial product, shift it left by the right number of zeros, and add it into a running total using string addition. Correct, but every digit of num2 triggers a full-length string addition of the running total — real repeated work that a single shared accumulator can avoid.
Time
O(n²)Space
O(n)Java
1class Solution {
2 public String multiplyStrings(String num1, String num2) {
3 if (num1.equals("0") || num2.equals("0")) return "0";
4 String result = "0";
5 for (int i = num2.length() - 1; i >= 0; i--) {
6 int digit = num2.charAt(i) - '0';
7 String partial = multiplyByDigit(num1, digit);
8 StringBuilder sb = new StringBuilder(partial);
9 for (int z = 0; z < num2.length() - 1 - i; z++) sb.append('0');
10 result = addStrings(result, sb.toString());
11 }
12 return result;
13 }
14 private String multiplyByDigit(String num, int digit) {
15 StringBuilder sb = new StringBuilder();
16 int carry = 0;
17 for (int i = num.length() - 1; i >= 0; i--) {
18 int prod = (num.charAt(i) - '0') * digit + carry;
19 sb.append(prod % 10);
20 carry = prod / 10;
21 }
22 if (carry > 0) sb.append(carry);
23 return sb.reverse().toString();
24 }
25 private String addStrings(String a, String b) {
26 StringBuilder sb = new StringBuilder();
27 int i = a.length() - 1, j = b.length() - 1, carry = 0;
28 while (i >= 0 || j >= 0 || carry > 0) {
29 int sum = carry;
30 if (i >= 0) sum += a.charAt(i--) - '0';
31 if (j >= 0) sum += b.charAt(j--) - '0';
32 sb.append(sum % 10);
33 carry = sum / 10;
34 }
35 return sb.reverse().toString();
36 }
37}Optimal — Position Array
OptimalSkip ever forming an intermediate partial-product string. Allocate one array of size m+n up front — multiplying digit i of num1 by digit j of num2 always contributes to exactly positions i+j and i+j+1 of the final product, no matter what the digit values are. Accumulate every digit pair's contribution directly into that single array with carrying, then read off the final string once at the end.
Time
O(n²)Space
O(n)Java
1class Solution {
2 public String multiplyStrings(String num1, String num2) {
3 if (num1.equals("0") || num2.equals("0")) return "0";
4 int m = num1.length(), n = num2.length();
5 int[] result = new int[m + n];
6 for (int i = m - 1; i >= 0; i--) {
7 for (int j = n - 1; j >= 0; j--) {
8 int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
9 int sum = mul + result[i + j + 1];
10 result[i + j + 1] = sum % 10;
11 result[i + j] += sum / 10;
12 }
13 }
14 StringBuilder sb = new StringBuilder();
15 for (int num : result) {
16 if (!(sb.length() == 0 && num == 0)) sb.append(num);
17 }
18 return sb.toString();
19 }
20}