Problem Statement

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 <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Logic

To solve this problem optimally, you can use an approach inspired by manual multiplication, employing a digit-by-digit multiplication method. Here’s the optimal Go solution:

Approach

Represent Multiplication as Arrays:
- Each digit of num1 is multiplied by each digit of num2, and the results are stored in a result array.
- The result array simulates how manual multiplication works.
Handle Carry:
- If any multiplication exceeds 9, carry is propagated to the next position in the result array.
Build the Result String:
- Convert the result array into a string, ensuring to remove leading zeros.

Complexity

Time Complexity: O(n×m), where n=len(nums1) and m=len(nums2).
Space Complexity: O(1), as no extra space is used apart from basic variables.

Golang solution

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}

	n1 := len(num1)
	n2 := len(num2)

	// digit by digit multiplication
	// total max length can be n1*n2
	result := make([]int, n1+n2)

	for i := n1 - 1; i >= 0; i-- {
		for j := n2 - 1; j >= 0; j-- {
			// look at '0' substracted from char to convert it to int
			mul := int(num1[i]-'0') * int(num2[j]-'0')
			sum := mul + result[i+j+1]

			result[i+j+1] = sum % 10
			result[i+j] += sum / 10
		}
	}

	var sb strings.Builder
	// strings.Builder
	// will help us to convert the byte buffer into string
	// sb.WriteByte is helpful
	// sb.String()

	fmt.Printf("result=%#v\n", result)
	// result=[]int{0, 5, 6, 0, 8, 8}

	for _, num := range result {
		// remove trailing zeroes
		if !(num == 0 && sb.Len() == 0) {
			// look at '0' added in integer num to convert it to char
			sb.WriteByte(byte(num + '0'))
		}
	}

	fmt.Printf("sb=%#v\n", sb)
	// sb=strings.Builder{addr:(*strings.Builder)(0xc00011fc88), buf:[]uint8{0x35, 0x36, 0x30, 0x38, 0x38}}

	fmt.Printf("sb=%#v\n", sb.String())
	// sb="56088"

	return sb.String()
}

Output

Input
num1 = "123"
num2 = "456"

Stdout
sb=strings.Builder{addr:(*strings.Builder)(0xc00011fc88), buf:[]uint8{0x35, 0x36, 0x30, 0x38, 0x38}}
sb="56088"
result=[]int{0, 5, 6, 0, 8, 8}

Output
"56088"

Please visit https: https://codeandalgo.com for more such contents.

CODE & ALGO

Multiply Strings

Table of Contents