1826. Base-B Column Sum
A ledger clerk adds two long counts that are written in the same base, anywhere from 2 to 36, using the digits 0 to 9 and then the lowercase letters a to z. The clerk works the way people do on paper: column by column from the right, writing the column digit and carrying into the next column whenever a column total reaches base.
Given the non-negative numbers a and b and the integer base, return their sum as text in that base. Neither input has leading zeros unless it is the single digit 0, and the sum must not have leading zeros either. 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 = "346", b = "777", base = 8
- Output:
- "1345"
- Explanation:
Column by column: 6+7=13 is 5 carry 1, 4+7+1=12 is 4 carry 1, 3+7+1=11 is 3 carry 1, and the last carry is 1, giving 1345.
Example 2
- Input:
- a = "zz", b = "1", base = 36
- Output:
- "100"
- Explanation:
z + 1 is 36, which is digit 0 carry 1 in base 36, and the carry repeats in the next column, giving 100.
Example 3
- Input:
- a = "0", b = "0", base = 2
- Output:
- "0"
- Explanation:
Zero plus zero is 0, written with a single digit.
Constraints
2 ≤ base ≤ 36
1 ≤ a.length, b.length ≤ 500
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)