Multiply Strings

Problem

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.

### Examples

Example 1

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2

Input: num1 = "123", num2 = "456"
Output: "56088"

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.

Solution

First read about - [Multiplication of Two Numbers](/maths/arithmetic/multiplication-of-two-numbers).

The key to solve this problem is multiplying each digit of the numbers from the right to left at the corresponding positions and get the sum values at each position. That is how we do multiplication manually.

Method 1 – Right to Left Multiplication (No Reversing)

Intuition

Since the numbers are large, we cannot use normal integer multiplication. Instead, we use the manual multiplication method: multiply each digit from right to left and sum the results at the correct positions, just like we do by hand.

Approach

1. Initialize an array of size n1 + n2 (where n1 and n2 are the lengths of num1 and num2) to store the intermediate results.
2. Multiply each digit of num1 (from right to left) with each digit of num2 (from right to left), and add the product to the correct position in the result array.
3. Handle the carry for each position in the result array.
4. Build the final string by skipping leading zeros.

Code

C++

#include <string>
#include <vector>
using namespace std;
string multiply(string num1, string num2) {
	int n1 = num1.size(), n2 = num2.size();
	vector<int> ans(n1 + n2, 0);
	for (int i = n1 - 1; i >= 0; --i) {
		for (int j = n2 - 1; j >= 0; --j) {
			int d1 = num1[i] - '0';
			int d2 = num2[j] - '0';
			ans[i + j + 1] += d1 * d2;
		}
	}
	int carry = 0;
	for (int i = n1 + n2 - 1; i >= 0; --i) {
		int tmp = (ans[i] + carry) % 10;
		carry = (ans[i] + carry) / 10;
		ans[i] = tmp;
	}
	string res;
	for (int num : ans) res += (num + '0');
	int idx = 0;
	while (idx < res.size() - 1 && res[idx] == '0') ++idx;
	return res.substr(idx);
}

Go

func multiply(num1 string, num2 string) string {
	n1, n2 := len(num1), len(num2)
	ans := make([]int, n1+n2)
	for i := n1 - 1; i >= 0; i-- {
		for j := n2 - 1; j >= 0; j-- {
			d1 := int(num1[i] - '0')
			d2 := int(num2[j] - '0')
			ans[i+j+1] += d1 * d2
		}
	}
	carry := 0
	for i := n1 + n2 - 1; i >= 0; i-- {
		tmp := (ans[i] + carry) % 10
		carry = (ans[i] + carry) / 10
		ans[i] = tmp
	}
	res := ""
	for _, num := range ans {
		res += string('0' + num)
	}
	idx := 0
	for idx < len(res)-1 && res[idx] == '0' {
		idx++
	}
	return res[idx:]
}

Java

public String multiply(String num1, String num2) {
	int n1 = num1.length(), n2 = num2.length();
	int[] ans = new int[n1 + n2];
	for (int i = n1 - 1; i >= 0; i--) {
		for (int j = n2 - 1; j >= 0; j--) {
			int d1 = num1.charAt(i) - '0';
			int d2 = num2.charAt(j) - '0';
			ans[i + j + 1] += d1 * d2;
		}
	}
	int carry = 0;
	for (int i = ans.length - 1; i >= 0; i--) {
		int tmp = (ans[i] + carry) % 10;
		carry = (ans[i] + carry) / 10;
		ans[i] = tmp;
	}
	StringBuilder sb = new StringBuilder();
	for (int num : ans) sb.append(num);
	while (sb.length() != 0 && sb.charAt(0) == '0') sb.deleteCharAt(0);
	return sb.length() == 0 ? "0" : sb.toString();
}

Kotlin

fun multiply(num1: String, num2: String): String {
	val n1 = num1.length
	val n2 = num2.length
	val ans = IntArray(n1 + n2)
	for (i in n1 - 1 downTo 0) {
		for (j in n2 - 1 downTo 0) {
			val d1 = num1[i] - '0'
			val d2 = num2[j] - '0'
			ans[i + j + 1] += d1 * d2
		}
	}
	var carry = 0
	for (i in n1 + n2 - 1 downTo 0) {
		val tmp = (ans[i] + carry) % 10
		carry = (ans[i] + carry) / 10
		ans[i] = tmp
	}
	val sb = StringBuilder()
	for (num in ans) sb.append(num)
	while (sb.length != 0 && sb[0] == '0') sb.deleteCharAt(0)
	return if (sb.isEmpty()) "0" else sb.toString()
}

Python

def multiply(num1: str, num2: str) -> str:
	n1, n2 = len(num1), len(num2)
	ans = [0] * (n1 + n2)
	for i in range(n1 - 1, -1, -1):
		for j in range(n2 - 1, -1, -1):
			d1 = int(num1[i])
			d2 = int(num2[j])
			ans[i + j + 1] += d1 * d2
	carry = 0
	for i in range(n1 + n2 - 1, -1, -1):
		tmp = (ans[i] + carry) % 10
		carry = (ans[i] + carry) // 10
		ans[i] = tmp
	res = ''.join(str(num) for num in ans)
	res = res.lstrip('0')
	return res if res else '0'

Rust

pub fn multiply(num1: String, num2: String) -> String {
	let n1 = num1.len();
	let n2 = num2.len();
	let mut ans = vec![0; n1 + n2];
	let num1 = num1.as_bytes();
	let num2 = num2.as_bytes();
	for i in (0..n1).rev() {
		for j in (0..n2).rev() {
			let d1 = (num1[i] - b'0') as i32;
			let d2 = (num2[j] - b'0') as i32;
			ans[i + j + 1] += d1 * d2;
		}
	}
	let mut carry = 0;
	for i in (0..n1 + n2).rev() {
		let tmp = (ans[i] + carry) % 10;
		carry = (ans[i] + carry) / 10;
		ans[i] = tmp;
	}
	let mut res = String::new();
	for &num in &ans {
		res.push((num as u8 + b'0') as char);
	}
	let res = res.trim_start_matches('0');
	if res.is_empty() { "0".to_string() } else { res.to_string() }
}

TypeScript

function multiply(num1: string, num2: string): string {
	const n1 = num1.length, n2 = num2.length;
	const ans = new Array(n1 + n2).fill(0);
	for (let i = n1 - 1; i >= 0; i--) {
		for (let j = n2 - 1; j >= 0; j--) {
			const d1 = Number(num1[i]);
			const d2 = Number(num2[j]);
			ans[i + j + 1] += d1 * d2;
		}
	}
	let carry = 0;
	for (let i = n1 + n2 - 1; i >= 0; i--) {
		const tmp = (ans[i] + carry) % 10;
		carry = Math.floor((ans[i] + carry) / 10);
		ans[i] = tmp;
	}
	let res = ans.join('');
	res = res.replace(/^0+/, '');
	return res.length === 0 ? '0' : res;
}

Complexity

• ⏰ Time complexity: O(n1 * n2), where n1 and n2 are the lengths of the input strings.
• 🧺 Space complexity: O(n1 + n2), for the result array.

Method 2 – Left to Right Multiplication (With Reversing)

Intuition

By reversing both input strings, we can process digits from least significant to most significant (left to right in the reversed strings), which simplifies indexing and carry handling. This approach is closer to how we multiply numbers by hand, but with the digits stored in reverse order.

Approach

1. Reverse both num1 and num2.
2. Use an array to store intermediate results, adding products and carries as we go.
3. After all multiplications, build the result string from the array, skipping leading zeros.

Code

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string multiply(string num1, string num2) {
	reverse(num1.begin(), num1.end());
	reverse(num2.begin(), num2.end());
	int n1 = num1.size(), n2 = num2.size();
	vector<int> result(n1 + n2, 0);
	for (int i = 0; i < n1; ++i) {
		int a = num1[i] - '0';
		int carry = 0;
		for (int j = 0; j < n2; ++j) {
			int b = num2[j] - '0';
			result[i + j] += a * b + carry;
			carry = result[i + j] / 10;
			result[i + j] %= 10;
		}
		result[i + n2] += carry;
	}
	string res;
	bool started = false;
	for (int i = n1 + n2 - 1; i >= 0; --i) {
		if (!started && result[i] == 0) continue;
		started = true;
		res += to_string(result[i]);
	}
	return res.empty() ? "0" : res;
}

Go

import "sort"
func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}
func multiply(num1 string, num2 string) string {
	num1 = reverse(num1)
	num2 = reverse(num2)
	n1, n2 := len(num1), len(num2)
	result := make([]int, n1+n2)
	for i := 0; i < n1; i++ {
		a := int(num1[i] - '0')
		carry := 0
		for j := 0; j < n2; j++ {
			b := int(num2[j] - '0')
			result[i+j] += a*b + carry
			carry = result[i+j] / 10
			result[i+j] %= 10
		}
		result[i+n2] += carry
	}
	res := ""
	started := false
	for i := n1 + n2 - 1; i >= 0; i-- {
		if !started && result[i] == 0 {
			continue
		}
		started = true
		res += string('0' + result[i])
	}
	if res == "" {
		return "0"
	}
	return res
}

Java

public String multiply(String num1, String num2) {
	num1 = new StringBuilder(num1).reverse().toString();
	num2 = new StringBuilder(num2).reverse().toString();
	int length1 = num1.length();
	int length2 = num2.length();
	int[] result = new int[length1 + length2];
	for (int i = 0; i < length1; i++) {
		int a = num1.charAt(i) - '0';
		int carry = 0;
		for (int j = 0; j < length2; j++) {
			int b = num2.charAt(j) - '0';
			result[i + j] += a * b + carry;
			carry = result[i + j] / 10;
			result[i + j] %= 10;
		}
		result[i + length2] += carry;
	}
	StringBuilder s = new StringBuilder();
	for (int i = length1 + length2 - 1; i >= 0; i--) {
		if (i != 0 && result[i] == 0 && s.length() == 0) continue;
		s.append(result[i]);
	}
	return s.toString();
}

Kotlin

fun multiply(num1: String, num2: String): String {
	val n1 = num1.length
	val n2 = num2.length
	val rev1 = num1.reversed()
	val rev2 = num2.reversed()
	val result = IntArray(n1 + n2)
	for (i in 0 until n1) {
		val a = rev1[i] - '0'
		var carry = 0
		for (j in 0 until n2) {
			val b = rev2[j] - '0'
			result[i + j] += a * b + carry
			carry = result[i + j] / 10
			result[i + j] %= 10
		}
		result[i + n2] += carry
	}
	val sb = StringBuilder()
	for (i in n1 + n2 - 1 downTo 0) {
		if (i != 0 && result[i] == 0 && sb.isEmpty()) continue
		sb.append(result[i])
	}
	return sb.toString()
}

Python

def multiply(num1: str, num2: str) -> str:
	rev1 = num1[::-1]
	rev2 = num2[::-1]
	n1, n2 = len(rev1), len(rev2)
	result = [0] * (n1 + n2)
	for i in range(n1):
		a = int(rev1[i])
		carry = 0
		for j in range(n2):
			b = int(rev2[j])
			result[i + j] += a * b + carry
			carry = result[i + j] // 10
			result[i + j] %= 10
		result[i + n2] += carry
	res = ''
	started = False
	for i in range(n1 + n2 - 1, -1, -1):
		if not started and result[i] == 0:
			continue
		started = True
		res += str(result[i])
	return res if res else '0'

Rust

pub fn multiply(num1: String, num2: String) -> String {
	let rev1: Vec<u8> = num1.bytes().rev().collect();
	let rev2: Vec<u8> = num2.bytes().rev().collect();
	let n1 = rev1.len();
	let n2 = rev2.len();
	let mut result = vec![0; n1 + n2];
	for i in 0..n1 {
		let a = (rev1[i] - b'0') as i32;
		let mut carry = 0;
		for j in 0..n2 {
			let b = (rev2[j] - b'0') as i32;
			result[i + j] += a * b + carry;
			carry = result[i + j] / 10;
			result[i + j] %= 10;
		}
		result[i + n2] += carry;
	}
	let mut res = String::new();
	let mut started = false;
	for i in (0..n1 + n2).rev() {
		if !started && result[i] == 0 {
			continue;
		}
		started = true;
		res.push_str(&result[i].to_string());
	}
	if res.is_empty() { "0".to_string() } else { res }
}

TypeScript

function reverse(s: string): string {
	return s.split('').reverse().join('');
}
function multiply(num1: string, num2: string): string {
	num1 = reverse(num1);
	num2 = reverse(num2);
	const n1 = num1.length, n2 = num2.length;
	const result = new Array(n1 + n2).fill(0);
	for (let i = 0; i < n1; i++) {
		const a = Number(num1[i]);
		let carry = 0;
		for (let j = 0; j < n2; j++) {
			const b = Number(num2[j]);
			result[i + j] += a * b + carry;
			carry = Math.floor(result[i + j] / 10);
			result[i + j] %= 10;
		}
		result[i + n2] += carry;
	}
	let res = '';
	let started = false;
	for (let i = n1 + n2 - 1; i >= 0; i--) {
		if (!started && result[i] === 0) continue;
		started = true;
		res += result[i].toString();
	}
	return res === '' ? '0' : res;
}

Complexity

• ⏰ Time complexity: O(n1 * n2), where n1 and n2 are the lengths of the input strings.
• 🧺 Space complexity: O(n1 + n2), for the result array.

Method 3 – Left to Right in Result Array (No Reversing)

Intuition

Instead of reversing the input strings, we can traverse the digits from the end (rightmost) and fill the result array from left to right. This approach keeps the original order of the input strings and only manipulates indices in the result array.

Approach

1. Traverse num1 and num2 from the end (rightmost digit) to the start.
2. For each digit, multiply and add to the correct position in the result array, handling carry as you go.
3. After all multiplications, build the result string from the result array, skipping leading zeros.

Code

C++

#include <string>
#include <vector>
using namespace std;
string multiply(string num1, string num2) {
	if (num1.empty() || num2.empty()) return "0";
	int n1 = num1.size(), n2 = num2.size();
	vector<int> result(n1 + n2, 0);
	for (int i = 0; i < n1; ++i) {
		int a = num1[n1 - i - 1] - '0';
		int carry = 0;
		for (int j = 0; j < n2; ++j) {
			int b = num2[n2 - j - 1] - '0';
			result[i + j] += a * b + carry;
			carry = result[i + j] / 10;
			result[i + j] %= 10;
		}
		result[i + n2] += carry;
	}
	string res;
	bool started = false;
	for (int i = n1 + n2 - 1; i >= 0; --i) {
		if (!started && result[i] == 0) continue;
		started = true;
		res += to_string(result[i]);
	}
	return res.empty() ? "0" : res;
}

Go

func multiply(num1 string, num2 string) string {
	if len(num1) == 0 || len(num2) == 0 {
		return "0"
	}
	n1, n2 := len(num1), len(num2)
	result := make([]int, n1+n2)
	for i := 0; i < n1; i++ {
		a := int(num1[n1-i-1] - '0')
		carry := 0
		for j := 0; j < n2; j++ {
			b := int(num2[n2-j-1] - '0')
			result[i+j] += a*b + carry
			carry = result[i+j] / 10
			result[i+j] %= 10
		}
		result[i+n2] += carry
	}
	res := ""
	started := false
	for i := n1 + n2 - 1; i >= 0; i-- {
		if !started && result[i] == 0 {
			continue
		}
		started = true
		res += string('0' + result[i])
	}
	if res == "" {
		return "0"
	}
	return res
}

Java

public String multiply(String num1, String num2) {
	if (num1 == null || num2 == null) {
		return null;
	}
	int length1 = num1.length();
	int length2 = num2.length();
	int[] result = new int[length1 + length2];
	for (int i = 0; i < length1; i++) {
		int a = num1.charAt(length1 - i - 1) - '0';
		int carry = 0;
		for (int j = 0; j < length2; j++) {
			int b = num2.charAt(length2 - j - 1) - '0';
			result[i + j] += a * b + carry;
			carry = result[i + j] / 10;
			result[i + j] %= 10;
		}
		result[i + length2] += carry;
	}
	StringBuilder s = new StringBuilder();
	for (int i = length1 + length2 - 1; i >= 0; i--) {
		if (i != 0 && result[i] == 0 && s.length() == 0) continue;
		s.append(result[i]);
	}
	return s.toString();
}

Kotlin

fun multiply(num1: String, num2: String): String {
	if (num1.isEmpty() || num2.isEmpty()) return "0"
	val n1 = num1.length
	val n2 = num2.length
	val result = IntArray(n1 + n2)
	for (i in 0 until n1) {
		val a = num1[n1 - i - 1] - '0'
		var carry = 0
		for (j in 0 until n2) {
			val b = num2[n2 - j - 1] - '0'
			result[i + j] += a * b + carry
			carry = result[i + j] / 10
			result[i + j] %= 10
		}
		result[i + n2] += carry
	}
	val sb = StringBuilder()
	for (i in n1 + n2 - 1 downTo 0) {
		if (i != 0 && result[i] == 0 && sb.isEmpty()) continue
		sb.append(result[i])
	}
	return sb.toString()
}

Python

def multiply(num1: str, num2: str) -> str:
	if not num1 or not num2:
		return '0'
	n1, n2 = len(num1), len(num2)
	result = [0] * (n1 + n2)
	for i in range(n1):
		a = int(num1[n1 - i - 1])
		carry = 0
		for j in range(n2):
			b = int(num2[n2 - j - 1])
			result[i + j] += a * b + carry
			carry = result[i + j] // 10
			result[i + j] %= 10
		result[i + n2] += carry
	res = ''
	started = False
	for i in range(n1 + n2 - 1, -1, -1):
		if not started and result[i] == 0:
			continue
		started = True
		res += str(result[i])
	return res if res else '0'

Rust

pub fn multiply(num1: String, num2: String) -> String {
	if num1.is_empty() || num2.is_empty() {
		return "0".to_string();
	}
	let n1 = num1.len();
	let n2 = num2.len();
	let num1 = num1.as_bytes();
	let num2 = num2.as_bytes();
	let mut result = vec![0; n1 + n2];
	for i in 0..n1 {
		let a = (num1[n1 - i - 1] - b'0') as i32;
		let mut carry = 0;
		for j in 0..n2 {
			let b = (num2[n2 - j - 1] - b'0') as i32;
			result[i + j] += a * b + carry;
			carry = result[i + j] / 10;
			result[i + j] %= 10;
		}
		result[i + n2] += carry;
	}
	let mut res = String::new();
	let mut started = false;
	for i in (0..n1 + n2).rev() {
		if !started && result[i] == 0 {
			continue;
		}
		started = true;
		res.push_str(&result[i].to_string());
	}
	if res.is_empty() { "0".to_string() } else { res }
}

TypeScript

function multiply(num1: string, num2: string): string {
	if (num1.length === 0 || num2.length === 0) return '0';
	const n1 = num1.length, n2 = num2.length;
	const result = new Array(n1 + n2).fill(0);
	for (let i = 0; i < n1; i++) {
		const a = Number(num1[n1 - i - 1]);
		let carry = 0;
		for (let j = 0; j < n2; j++) {
			const b = Number(num2[n2 - j - 1]);
			result[i + j] += a * b + carry;
			carry = Math.floor(result[i + j] / 10);
			result[i + j] %= 10;
		}
		result[i + n2] += carry;
	}
	let res = '';
	let started = false;
	for (let i = n1 + n2 - 1; i >= 0; i--) {
		if (!started && result[i] === 0) continue;
		started = true;
		res += result[i].toString();
	}
	return res === '' ? '0' : res;
}

Complexity

• ⏰ Time complexity: O(n1 * n2), where n1 and n2 are the lengths of the input strings.
• 🧺 Space complexity: O(n1 + n2), for the result array.