You get an array digits that holds a whole number, one digit per element. Return the digits of that number plus one.
The first digit is the leftmost one, as you would write the number. Your answer keeps that order.
The number never starts with a 0. The only exception is 0 itself, given as [0].
Example 1:
Input: digits = [6,0,4] Output: [6,0,5] Explanation: The number is 604. 604 + 1 = 605.
Example 2:
Input: digits = [2,4,9,9] Output: [2,5,0,0] Explanation: The number is 2499. 2499 + 1 = 2500. Both 9s turn into 0s, and the 4 becomes a 5.
Example 3:
Input: digits = [9,9,9] Output: [1,0,0,0] Explanation: 999 + 1 = 1000. The answer has one more digit than the input.
Constraints:
- 1 to 100,000 digits.
- Each digit is from 0 to 9.
- The first digit is 0 only when the number is 0.
Your solution should run in O(n) time for n digits. Besides the answer, it should use O(1) extra space.
Add 1 the way you would on paper. Start at the last digit. A digit below 9 just grows by one, and you are done.
A 9 plus 1 makes 10. Write 0 there and carry the 1 to the digit on its left. If every digit was a 9, the carry becomes a new first digit: 1.
Each digit is visited at most once, from right to left: O(n) time.
The digits change in place. Only when all of them are 9 does the answer grow by one digit, a 1 in front.
Apart from the answer, we keep only the loop index, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
