Multiply Strings

Medium

The problem

num1 and num2 are non-negative whole numbers written as strings. Return their product, also as a string. Do not convert the whole strings to integers, because they can be far too long for any built-in number type.

Example 1
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2
Input: num1 = "123", num2 = "456"
Output: "56088"

Limits

1 ≤ len(num1), len(num2) ≤ 200
Only digits 0 to 9, no leading zeros except for "0" itself
The result has no leading zeros either

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Do it like on paper: digit i times digit j lands in position i+j and i+j+1.

The idea

Result array of length m+n; add each product into position i+j+1 and carry into i+j; then strip leading zeros.

Target: O(m·n) time

Go function shape

func multiply(num1 string, num2 string) string

Reference solution

Tested with go test. Try it yourself first, then compare.

// Multiply: multiply two numbers given as strings, digit by digit like on paper.
// Digit i of a times digit j of b lands in result position i+j+1 (carry goes to i+j).
func Multiply(a, b string) string {
	if a == "0" || b == "0" {
		return "0"
	}
	res := make([]int, len(a)+len(b))
	for i := len(a) - 1; i >= 0; i-- {
		for j := len(b) - 1; j >= 0; j-- {
			sum := int(a[i]-'0')*int(b[j]-'0') + res[i+j+1]
			res[i+j+1] = sum % 10
			res[i+j] += sum / 10
		}
	}
	out := make([]byte, 0, len(res))
	for i, d := range res {
		if i == 0 && d == 0 {
			continue // strip the single possible leading zero
		}
		out = append(out, byte('0'+d))
	}
	return string(out)
}

Read the lesson: Bit Manipulation & Math