Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/43.html
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
andnum2
consist of digits only.- Both
num1
andnum2
do not contain any leading zero, except the number0
itself.
Algorithm
The length of the product obtained by multiplying two numbers does not
actually exceed the sum of the lengths of the two numbers. If the length of num1
is m
and the length of num2
is n
, the length of num1 * num2
will not exceed m+n
.
To understand why it is misplaced when multiplying, consider the example of 6 multiplied by 8, which produces 48. If we incorrectly add the result of multiplying 6 by 9, which is 54, it is because 8 is a number in the tens place, which is equivalent to 80. So the result in the ones place actually needs a 0 at the end. It is also important to observe that if two digits at any position in num1
and num2
are multiplied, the position of the two digits obtained in the final result is determined. For example, if the number at position i in num1
is multiplied by the number at position j in num2
, then the positions of the two digits obtained are i+j and i+j+1. Once these concepts are understood, misplaced addition can be performed and the final result can be accumulated.
To implement this algorithm, the multiplication starts from the ones digit and traverses from the end of the num1
and num2
strings to extract the characters at the corresponding positions respectively, convert them to integers, and multiply them. Then the positions p1
and p2
where the two digits after the multiplication are located are determined. Since p2
is lower than p1
, the two digits obtained are added to the position of p2
first. This may cause the number at position p2
to be greater than 9, so the number in the ten’s place must be added to the high-order p1
, and only the remainder is left in the p2
position, so that the number in each place becomes one. The next step is to store the number in the result res
starting from the high bit, while skipping any leading zeros. Finally, the corner case of an empty result res
is handled by returning “0”, otherwise the result is returned.
Code
-
import java.math.BigInteger; import java.util.Arrays; public class Multiply_Strings { public static void main(String[] args) { int n = '9' - '0'; System.out.println(n); Multiply_Strings out = new Multiply_Strings(); Solution s = out.new Solution(); System.out.println(s.multiply("123", "456")); } public class Solution { public String multiply(String num1, String num2) { // validation as to according to description, should also check length<110 and no leading zero if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) { return ""; } // @note: proof: 999 * 999 = (1000 - 1)^2 < 1000^2=1000000 // i.e.: n1*n2 < 10^(len1+len2) <=> n1*n2 <= 999...99(length=len1+len2) int[] result = new int[num1.length() + num2.length()]; // @note: reverse is better for store in results, or else reverse direction is annoying String n1 = new StringBuilder(num1).reverse().toString(); String n2 = new StringBuilder(num2).reverse().toString(); int carry = 0; int i = 0; // @note: for final check int j = 0; // @note: for final check for ( ; i < n1.length(); i++) { carry = 0; // @note: i missed this one, every out loop should update carry! int d1 = n1.charAt(i) - '0'; // digit of n1 // for (; j < n2.length(); j++) { // @note: here j is not re-set to 0 in another i-loop // that's why I like while() !!! for ( ; j < n2.length(); j++) { // first calculate this d1*n2 int d2 = n2.charAt(j) - '0'; int single = d1 * d2; int addCarry = single + carry; // add up to result array // i is also the indicator of start index in result array result[i + j] += addCarry; // @note: careful using if-else, and if carry<10 it's not updated // if (single >= 10) { // carry += result[i + j] / 10; // single = result[i + j] % 10; // } carry = result[i + j] / 10; result[i + j] = result[i + j] % 10; } // @note: outside inner loop, there should be a final check (not outside both for-loop) // eg.123*456 if (carry > 0) { // j is ++ already result[i + j] = carry; } } // restore as string String m = ""; for (i = 0; i < result.length; i++) { m = result[i] + m; } while (m.length() > 1 && m.charAt(0) == '0') { m = m.substring(1); } return m; } } // but theoretical still overflow possibility public class Solution_big_integer { public String multiply(String num1, String num2) { BigInteger a = new BigInteger(num1); BigInteger b = new BigInteger(num2); a = a.multiply(b); return a.toString(); } } } ############ class Solution { public String multiply(String num1, String num2) { if ("0".equals(num1) || "0".equals(num2)) { return "0"; } int m = num1.length(), n = num2.length(); int[] arr = new int[m + n]; for (int i = m - 1; i >= 0; --i) { int a = num1.charAt(i) - '0'; for (int j = n - 1; j >= 0; --j) { int b = num2.charAt(j) - '0'; arr[i + j + 1] += a * b; } } for (int i = arr.length - 1; i > 0; --i) { arr[i - 1] += arr[i] / 10; arr[i] %= 10; } int i = arr[0] == 0 ? 1 : 0; StringBuilder ans = new StringBuilder(); for (; i < arr.length; ++i) { ans.append(arr[i]); } return ans.toString(); } }
-
// OJ: https://leetcode.com/problems/multiply-strings/ // Time: O(MN) // Space: O(M + N) class Solution { string mul(const string &a, int n, int shift) { if (n == 0 || a == "0") return "0"; int carry = 0; string ans; for (int N = a.size(), i = N - 1; i >= 0 || carry;) { if (i >= 0) carry += (a[i--] - '0') * n; ans += carry % 10 + '0'; carry /= 10; } reverse(begin(ans), end(ans)); while (shift--) ans += '0'; return ans; } string add(string a, string b) { if (a == "0") return b; if (b == "0") return a; string ans; for (int i = a.size() - 1, j = b.size() - 1, carry = 0; i >= 0 || j >= 0 || carry; ) { if (i >= 0) carry += a[i--] - '0'; if (j >= 0) carry += b[j--] - '0'; ans += carry % 10 + '0'; carry /= 10; } reverse(begin(ans), end(ans)); return ans; } public: string multiply(string a, string b) { string ans = "0"; for (int i = 0, N = b.size(); i < N; ++i) { ans = add(ans, mul(a, b[N - 1 - i] - '0', i)); } return ans; } };
-
class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) arr = [0] * (m + n) for i in range(m - 1, -1, -1): a = int(num1[i]) for j in range(n - 1, -1, -1): b = int(num2[j]) arr[i + j + 1] += a * b for i in range(m + n - 1, 0, -1): arr[i - 1] += arr[i] // 10 arr[i] %= 10 i = 0 if arr[0] else 1 return "".join(str(x) for x in arr[i:]) ############ class Solution(object): def multiply(self, num1, num2): """ :type num1: str :type num2: str :rtype: str """ ans = [0] * (len(num1) + len(num2)) for i, n1 in enumerate(reversed(num1)): for j, n2 in enumerate(reversed(num2)): ans[i + j] += int(n1) * int(n2) ans[i + j + 1] += ans[i + j] / 10 ans[i + j] %= 10 while len(ans) > 1 and ans[-1] == 0: ans.pop() return "".join(map(str, ans[::-1]))
-
func multiply(num1 string, num2 string) string { if num1 == "0" || num2 == "0" { return "0" } m, n := len(num1), len(num2) arr := make([]int, m+n) for i := m - 1; i >= 0; i-- { a := int(num1[i] - '0') for j := n - 1; j >= 0; j-- { b := int(num2[j] - '0') arr[i+j+1] += a * b } } for i := len(arr) - 1; i > 0; i-- { arr[i-1] += arr[i] / 10 arr[i] %= 10 } i := 0 if arr[0] == 0 { i = 1 } ans := []byte{} for ; i < len(arr); i++ { ans = append(ans, byte('0'+arr[i])) } return string(ans) }
-
function multiply(num1: string, num2: string): string { if ([num1, num2].includes('0')) return '0'; const n1 = num1.length, n2 = num2.length; let ans = ''; for (let i = 0; i < n1; i++) { let cur1 = parseInt(num1.charAt(n1 - i - 1), 10); let sum = ''; for (let j = 0; j < n2; j++) { let cur2 = parseInt(num2.charAt(n2 - j - 1), 10); sum = addString(sum, cur1 * cur2 + '0'.repeat(j)); } ans = addString(ans, sum + '0'.repeat(i)); } return ans; } function addString(s1: string, s2: string): string { const n1 = s1.length, n2 = s2.length; let ans = []; let sum = 0; for (let i = 0; i < n1 || i < n2 || sum > 0; i++) { let num1 = i < n1 ? parseInt(s1.charAt(n1 - i - 1), 10) : 0; let num2 = i < n2 ? parseInt(s2.charAt(n2 - i - 1), 10) : 0; sum += num1 + num2; ans.unshift(sum % 10); sum = Math.floor(sum / 10); } return ans.join(''); }
-
using System.Text; public class Solution { public string Multiply(string num1, string num2) { var digits = new int[num1.Length + num2.Length]; for (var i = 0; i < num1.Length; ++i) { for (var j = 0; j < num2.Length; ++j) { var digit1 = num1[num1.Length - i - 1] - '0'; var digit2 = num2[num2.Length - j - 1] - '0'; var product = digit1 * digit2; digits[i + j] += product; } } var carry = 0; for (var i = 0; i < digits.Length; ++i) { digits[i] += carry; carry = digits[i] / 10; digits[i] %= 10; } var sb = new StringBuilder(); for (var i = digits.Length - 1; i >= 0; --i) { if (digits[i] > 0 || sb.Length > 0) { sb.Append((char)(digits[i] + '0')); } } if (sb.Length == 0) sb.Append('0'); return sb.ToString(); } }
-
impl Solution { pub fn multiply(num1: String, num2: String) -> String { if num1 == "0" || num2 == "0" { return String::from("0"); } let (num1, num2) = (num1.as_bytes(), num2.as_bytes()); let (n, m) = (num1.len(), num2.len()); let mut res = vec![]; for i in 0..n { let a = num1[n - i - 1] - b'0'; let mut sum = 0; let mut j = 0; while j < m || sum != 0 { if i + j == res.len() { res.push(0) } let b = num2.get(m - j - 1).unwrap_or(&b'0') - b'0'; sum += a * b + res[i + j]; res[i + j] = sum % 10; sum /= 10; j += 1; } } res.into_iter() .rev() .map(|v| char::from(v + b'0')) .collect() } }