Plus One
Easy· digit arithmetic
Problem
A non-negative integer is stored as an array of digits, most significant first, with no leading zeros. Add one to the number and return the resulting digit array.
Examples
Input: digits = [1,2,3]
Output: [1,2,4]
Input: digits = [9,9,9]
Output: [1,0,0,0]
Constraints
- • 1 <= digits.length <= 100
- • 0 <= digits[i] <= 9
Hints & approach
Hint 1
Converting to a number overflows for long arrays.
Hint 2
Work from the last digit, just like adding by hand.
Hint 3
A 9 becomes 0 and carries; anything else just increments and you are done.
Approachtry the hints first
Walk from the least significant digit. If the digit is below 9, increment it and return immediately. Otherwise set it to 0 and continue carrying to the left. If every digit was 9, the loop finishes without returning, so prepend a 1 to the now all-zero array.
Time O(n) · Space O(1) (O(n) only when all digits are 9)