1822. Carry Counter
A teacher marks column addition and wants to know how many carries each exercise needs. The numbers a and b are written as text in the same base, anywhere from 2 to 36, using the digits 0 to 9 and then the lowercase letters a to z. Adding column by column from the right, a column produces a carry when its digit total, including any carry coming in, reaches base.
Return how many columns produce a carry. A carry out of the leftmost column counts too. Neither input has leading zeros unless it is the single digit 0. Aim for O(n + m) time and O(1) extra space, where n and m are the lengths of a and b. There is no need to build the sum itself.
Example 1
- Input:
- a = "999", b = "1", base = 10
- Output:
- 3
- Explanation:
All three columns produce a carry.
Example 2
- Input:
- a = "123", b = "456", base = 10
- Output:
- 0
- Explanation:
No column total reaches 10, so there is no carry.
Example 3
- Input:
- a = "111", b = "1", base = 2
- Output:
- 3
- Explanation:
1+1 carries, then 1+1 carries, then 1+1 carries, so three carries.
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(1)