You get two strings, num1 and num2. Each one holds a whole number written in digits.
Return the product of the two numbers, also as a string. It has no zeros in front, so a product of 0 is "0".
A number can have up to 1,000 digits. Numbers that long don't fit in the usual integer types. So don't turn a whole string into a number. Work with its digits instead.
Example 1:
Input: num1 = "25", num2 = "16" Output: "400" Explanation: 25 times 16 is 400.
Example 2:
Input: num1 = "999", num2 = "99" Output: "98901" Explanation: 999 times 99 is 98901. The answer has 5 digits, as many as both numbers together.
Example 3:
Input: num1 = "0", num2 = "8317" Output: "0" Explanation: Any number times 0 is 0. The answer is "0", with no extra zeros.
Constraints:
num1andnum2each have 1 to 1,000 digits.- They hold only the digits 0 to 9.
- Neither starts with 0, unless it is the number 0.
Your solution should run in O(m · n) time. Here m and n are the lengths of num1 and num2.
Multiply the way you learned at school. Each digit of
num1 meets each digit of num2 once. Two digits make at most 81.
Number the positions of the answer from the left, starting at 0. With
m and n digits, there are m + n positions. The product of digit i of num1 and digit j of num2 lands at position i + j + 1. Its tens carry into position i + j.
Every pair of digits takes one step: O(m · n) time.
The answer has at most
m + n digits, so the extra space is O(m + n).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
