DSA problem
Plus One
You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the integer in most-significant-to-least-significant order. The leading digit is non-zero except for the special number zero itself. Your task is to increment the number by one and return the resulting array of digits.
A naive approach would convert the array into a numeric type, add one, then convert the result back into digits. That breaks down quickly: the input length can be up to one hundred digits, so the integer easily exceeds what fits in a 64-bit primitive. We need a purely digit-based algorithm.
The correct way to add one to a multi-digit number is to imagine the classic schoolbook addition: start from the least significant digit, add the increment, and propagate any carry to the left. If a digit is less than nine we can simply increment it and return — there is no carry, so every higher digit stays the same.
If the digit is nine, adding one turns it into ten, which means we write a zero in place and carry one to the next position. This continues as long as we see nines. In the worst case (all nines, like 999) the carry propagates all the way past the most significant digit, which means the result has one more digit than the input and we must prepend a leading one. The algorithm is a single right-to-left pass in O(n) time with O(1) extra working space.
Examples
digits = [1,2,3][1,2,4]digits = [4,3,2,1][4,3,2,2]digits = [9][1,0]Constraints
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits does not contain any leading 0's, except the number 0 itself.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.