The problem
A large number is stored as an array of its digits, most significant first. Add one to it and return the new digits.
Examples
01
- Input
digits = [1, 2, 3]
- Output
[1, 2, 4]
02
- Input
digits = [4, 3, 2, 1]
- Output
[4, 3, 2, 2]
03
- Input
digits = [9]
- Output
[1, 0]
Constraints
- 1 ≤ digits.length ≤ 100
- 0 ≤ digits[i] ≤ 9
- No leading zeros.
The idea
Add as on paper, from the last digit. A digit below 9 just goes up by one, and the job is done. A 9 becomes 0 and carries 1 to the digit on its left.
If every digit was 9 — like 999 — every one becomes 0 and the carry falls off the front: the answer is 1 followed by all those zeros, 1000.
- Time
- O(n)
- Space
- O(1), or O(n) when the number grows a digit
Solution · every language run against every case
class Solution: def plusOne(self, digits: List[int]) -> List[int]: for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: digits[i] += 1 # no carry: done return digits digits[i] = 0 # 9 + 1 = 10: write 0, carry 1 leftwards return [1] + digits # every digit was 9: the number grows a digit