299. Chain Addition
Two huge non-negative numbers are stored digit by digit in chains, with the least significant digit first. So the chain 4, 0, 2 stands for the number 204. Each node holds a single digit from 0 to 9, and the numbers are far too long for a built-in integer type.
Given the heads a and b, add the two numbers and return the sum as a chain in the same orientation (least significant digit first). The input chains may contain extra zeros at their high end, but the result must be written in standard form: no unnecessary high-order zeros, and the number zero is the single node 0. Both chains have between 1 and 100,000 nodes.
Example 1
- Input:
- a = [7,9,4], b = [5,3]
- Output:
- [2,3,5]
- Explanation:
497 + 35 = 532, written least significant first as 2, 3, 5.
Example 2
- Input:
- a = [9,9,9,9], b = [6,0,0,0]
- Output:
- [5,0,0,0,1]
- Explanation:
9999 + 6 = 10005, so the carry ripples out and the result is 5, 0, 0, 0, 1.
Constraints
1 ≤ length of each chain ≤ 105
0 ≤ node value ≤ 9
The first node is the least significant digit.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(max(n, m))
- Space
- O(max(n, m))