1828. Base-B Long Product
A teaching tool shows pupils how long multiplication works in other bases. Numbers are written as text in a base between 2 and 36, using the digits 0 to 9 and then the lowercase letters a to z. The tool multiplies digit by digit, keeping a carry, exactly like the paper method.
Given the non-negative numbers a and b and the integer base, return their product as text in that base. Neither input has leading zeros unless it is the single digit 0, and the product must not have leading zeros either; anything times 0 is 0. Do not convert the strings to built-in integers. Aim for O(n * m) time, where n and m are the lengths of a and b.
Example 1
- Input:
- a = "234", b = "76", base = 8
- Output:
- "22710"
- Explanation:
234 (octal) is 156 and 76 (octal) is 62, the product is 9672, which is 22710 in octal.
Example 2
- Input:
- a = "ff", b = "ff", base = 16
- Output:
- "fe01"
- Explanation:
255 * 255 = 65025, which is fe01 in hexadecimal.
Example 3
- Input:
- a = "z", b = "0", base = 36
- Output:
- "0"
- Explanation:
Anything times zero is 0.
Constraints
2 ≤ base ≤ 36
1 ≤ a.length, b.length ≤ 300
every digit is smaller than base; no leading zeros except the single string "0"
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n * m)
- Space
- O(n + m)