1829. Base Hopper
A converter box receives a non-negative number written as text in base fromBase and must reprint it in base toBase. Bases run from 2 to 36 and the digits are 0 to 9 followed by the lowercase letters a to z. The numbers can be much longer than any machine integer, so the box cannot go through a built-in integer type.
Given digits, fromBase and toBase, return the same number written in base toBase. The input has no leading zeros unless it is the single digit 0, and the output must not have leading zeros either. A good approach divides the whole digit list by toBase again and again, collecting remainders. Aim for O(n^2) time where n is the length of digits.
Example 1
- Input:
- digits = "24", fromBase = 8, toBase = 2
- Output:
- "10100"
- Explanation:
24 in octal is 20, which is 10100 in binary.
Example 2
- Input:
- digits = "zz", fromBase = 36, toBase = 16
- Output:
- "50f"
- Explanation:
35*36 + 35 = 1295, which is 50f in hexadecimal.
Example 3
- Input:
- digits = "0", fromBase = 2, toBase = 10
- Output:
- "0"
- Explanation:
Zero stays 0 in every base.
Constraints
2 ≤ fromBase, toBase ≤ 36
1 ≤ digits.length ≤ 400
every digit is smaller than fromBase; 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^2)
- Space
- O(n)