Plus One
The key idea
Walk the digits from right to left. If a digit is less than
9, add one and you are done — there is no carry. Only a 9 rolls over to 0 and pushes a carry left. If every digit is 9, the carry escapes the front, so prepend a 1.Problem
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant, left to right. The integer does not contain any leading zeros except for the number 0 itself.
Increment the large integer by one and return the resulting array of digits.
Constraints
1 <= digits.length <= 1000 <= digits[i] <= 9digitsdoes not contain any leading zeros except for the number0itself.
Examples
Input: digits = [1,2,3]
Output: [1,2,4]
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Input: digits = [9]
Output: [1,0]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Math / Number Theory problems
- Add BinaryEASY
- Factorial Trailing ZeroesMEDIUM
- Excel Sheet Column TitleEASY
- Greatest Common Divisor of StringsEASY
- Integer to RomanMEDIUM
- Multiply StringsMEDIUM
- Palindrome NumberEASY
- Reverse IntegerMEDIUM
- Roman to IntegerEASY