Plus One
Easy · Math · Array · Math
Problem
A non-negative integer is stored as an array digits, one decimal digit per element, with the most significant digit first. The number has no leading zeros, except for the number 0 itself.
Add one to the number and return the result in the same digit-array form. A carry can ripple through a run of 9s and make the result one digit longer.
Examples
Input: digits = [2,4,7] Output: [2,4,8]
247 + 1 = 248, so only the last digit changes.
Input: digits = [3,9,9] Output: [4,0,0]
The carry from the trailing 9s turns 399 into 400.
Input: digits = [9,9] Output: [1,0,0]
99 + 1 = 100, which needs an extra leading digit.
Constraints
- 1 <= len(digits) <= 100
- 0 <= digits[i] <= 9
- digits has no leading zeros
Approaches
- Full column addition over every digit — time O(n), space O(n)
Follow-up
What if the digits were stored least significant first, or in a linked list? Least significant first, the carry walks forward from index 0 and a new digit is appended at the end. In a singly linked list stored most significant first, find the last node that is not a 9: add one to it and zero everything after it.
Related problems
Start free on Cariara · Coding problems · System design studio
