Description
A non-empty decimal digit array represents a nonnegative integer in normal, most-significant-first order, without unnecessary leading zeros. Return its digits after adding one.
Solution
def plus_one(digits):
result = digits.copy()
for i in range(len(result) - 1, -1, -1):
if result[i] < 9:
result[i] += 1
return result
result[i] = 0
return [1] + resultExamples
Example 1
- Input
[[1,2,3]]- Output
[1,2,4]
Increment the last digit.
Example 2
- Input
[[9,9]]- Output
[1,0,0]
The carry extends the number.
Example 3
- Input
[[0]]- Output
[1]
Zero becomes one.
Approach
Copy the digits and propagate a carry from the right. The first digit smaller than 9 increments and stops the process; trailing 9s become zero. If all digits were 9, prepend a 1.
Time & space
O(n) time and O(n) auxiliary space for the copied digits, where n is digit count.