66. Plus One

Problem¶

Given a non-empty list of decimal digits representing an integer, return the digits after adding one.

Example:

[1, 2, 9] -> [1, 3, 0]
# because 129 + 1 = 130

Key trick¶

Walk from right to left and stop as soon as a digit is not 9.

• If the current digit is < 9, increment it and return.
• If it is 9, set it to 0 and keep carrying.
• If all digits were 9, prepend 1.

Trap¶

Common mistakes:

• Converting to int and back.
• Works in Python, but misses the intended carry logic.
• Forgetting the all-9 case.
• Example: [9, 9] -> [1, 0, 0].
• Rebuilding the whole result when an in-place update is enough.
• Mutating input unexpectedly if the caller cares about reuse.

Why is it interesting?¶

It is a tiny carry-propagation problem.

• It tests digit manipulation.
• It rewards early return.
• It is a simple example of right-to-left state propagation.

Python solution¶

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        # Traverse from the least significant digit.
        for i in range(len(digits) - 1, -1, -1):
            # No carry after increment: done immediately.
            if digits[i] < 9:
                digits[i] += 1
                return digits

            # 9 + 1 becomes 0 with carry to the left.
            digits[i] = 0

        # If we get here, every digit was 9.
        return [1] + digits

Comment on my solution¶

Your solution is correct and handles carry well.

Good points:

• Correct carry propagation.
• Correct all-9 handling.
• Clear arithmetic with % 10 and // 10.

Possible simplifications:

• You do not need a separate out list.
• In-place right-to-left update is shorter and easier to read.
• Your test has one duplicated case: [4,3,2,1].

import pytest

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        l = len(digits)
        d = 1
        out = []
        for i in range(l):
            out.append((digits[l - 1 - i] + d) % 10)
            d = (digits[l - 1 - i] + d) // 10
        if d:
            out.append(d)
        out.reverse()
        return out


@pytest.mark.parametrize(
    ("digits", "expected"),
    [
        ([1,2,3], [1,2,4]),
        ([4,3,2,1], [4,3,2,2]),
        ([4,3,2,1], [4,3,2,2]),
        ([9], [1,0]),
        ([9,9,9], [1,0,0,0]),
        ([1,9,9], [2,0,0]),
        ([9,8,7,6,5,4,3,2,1,0], [9,8,7,6,5,4,3,2,1,1])
    ]
)
def test_plusOne(digits, expected):
    assert Solution().plusOne(digits) == expected

Extra¶

Meaning of "to carry" in algorithm description¶

In an algorithm, "to carry" refers to the same idea as in basic arithmetic: when a value exceeds the maximum allowed for a digit or position, the extra amount is passed to the next higher position.

For example, in base-10:

• If you add 1 to 9, you get 10
• You write 0 in the current position and carry 1 to the next position

So in your original sentence:

"If it is 9, set it to 0 and keep carrying"

It means:

• Reset the current digit to 0
• Then propagate a +1 to the next digit, possibly repeating the process if that digit is also 9

This is commonly used in algorithms that simulate:

• Addition
• Incrementing numbers stored as arrays
• Odometer-style counting systems

In short: "carry" = pass overflow to the next position.