334. Double the Chain Number
A museum counts its visitors on an old odometer whose wheels are stored as a chain of nodes. Every node holds one decimal digit from 0 to 9, and the chain is read from the most significant digit at head to the least significant digit at the end. The chain therefore spells a non-negative whole number.
The curator decides that the true count is exactly twice what the odometer shows. Return the chain of digits that spells the doubled number, again with the most significant digit first. The number has no leading zeros, except that the number zero itself is a single node 0, and the answer must follow the same rule. The number can have up to 100,000 digits, so you cannot convert it to a built-in integer.
Example 1
- Input:
- head = [3,7,4,8]
- Output:
- [7,4,9,6]
- Explanation:
3748 doubled is 7496.
Example 2
- Input:
- head = [8,6,5]
- Output:
- [1,7,3,0]
- Explanation:
865 doubled is 1730, which needs one more digit than the input.
Constraints
1 ≤ chain length ≤ 105
0 ≤ node value ≤ 9
The first node is not 0 unless the chain is a single node.
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)