Add one to a number stored as an array of digits. Start from the right, turn each 9 into 0 and carry, and grow the array if needed.
▼The problem
LeetCode 66 (Easy). A large integer is given as an array digits, most significant digit first, with no leading zeros. Add one to the integer and return the resulting array of digits.
Examples (LeetCode's): [1,2,3] → [1,2,4], [4,3,2,1] → [4,3,2,2] and [9] → [1,0].
The solution
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
return [1] + digitsTranscript
Plus One. A huge number is stored as an array of digits, most significant first. Add one, and return the new digits.
One, two, three becomes one, two, four. Four, three, two, one becomes four, three, two, two. And nine becomes one, zero: the array grew.
The easy way: join the digits into an integer, add one, split it back. Python's big integers handle that. But the input can have a hundred digits, and a sixty-four-bit integer holds only nineteen, so most languages overflow.
Instead, add one like on paper: from the right. Picture each digit as a bucket that holds up to nine. Drip one into the last bucket. Below nine, it just rises, and we're done. A full nine overflows: empty it to zero, and carry one left.
In code, walk i from the last index down. If digits at i is below nine, add one and return. Otherwise, set it to zero and keep going. If the loop finishes, every digit was nine, so put a one in front.
Try one, nine, nine. The last nine spills to zero. The middle nine spills too. The one becomes two: two, zero, zero. Now nine, nine, nine. All three spill, the loop ends, and a new bucket holding one appears: one, zero, zero, zero.
We stop at the first digit below nine: order n time at worst. Extra space is order one, unless every digit is nine and we need a new array.
Start at the right, spill the nines, carry the one. That's Plus One.