Plus One
A non-negative integer is stored as a list of its decimal digits, most significant digit first. For example 129 is [1, 2, 9]. The number has no leading zeros, except that zero itself is [0].
Return the digits of the number plus one. The number can be far too large for a 64-bit integer, so work on the digits.
Examples
Input digits = [1, 2, 3]
Output [1, 2, 4]
Input digits = [1, 2, 9]
Output [1, 3, 0]
The 9 becomes 0 and carries into the 2.
Input digits = [9, 9]
Output [1, 0, 0]
The carry creates a new leading digit.
Constraints
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits has no leading zero, except for the single digit 0
Stuck? Take one hint at a time
Common mistakes
- Turning the digits into an integer, adding one, and splitting it again, which overflows in languages with fixed size integers for numbers of 100 digits.
- Forgetting the all nines case, so [9, 9] returns [0, 0].
- Carrying to the right instead of the left, or starting from the first digit.
- Not stopping after the carry is absorbed, which keeps changing digits that should stay.
Questions an interviewer may ask next
- Add two numbers given as digit lists of different lengths. (The same carry, with two pointers.)
- Add one to a number stored with the least significant digit first. (Walk from the start instead.)
- Add one to a number stored as a linked list of digits. (Reverse it, or use recursion or a stack.)
- Add an arbitrary k, not just one. What bounds the carry? (The carry can be as long as k itself, so the answer may be longer by the number of digits of k.)
digits
[1,2,3]
Expected output
[1,2,4]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.