LeetCode 66: Plus One

Problem Restatement

We are given a large integer represented as an array of digits.

The digits are ordered from most significant to least significant. This means the leftmost digit is the largest place value.

We need to add one to the integer and return the resulting digits as an array.

The input has no leading zeroes, and each element is a single digit from 0 to 9. The official constraints are 1 <= digits.length <= 100 and 0 <= digits[i] <= 9.

Input and Output

Function shape:

def plusOne(digits: list[int]) -> list[int]:
    ...

Examples

For:

digits = [1, 2, 3]

The array represents:

123

After adding one:

123 + 1 = 124

So the answer is:

[1, 2, 4]

For:

digits = [4, 3, 2, 1]

The number is 4321.

After adding one, it becomes 4322.

So the answer is:

[4, 3, 2, 2]

For:

digits = [9]

The number is 9.

After adding one:

9 + 1 = 10

So the answer is:

[1, 0]

First Thought: Convert to Integer

One simple idea is:

1. Convert the digit array into an integer.
2. Add one.
3. Convert the integer back into an array.

For example:

digits = [1, 2, 3]
number = 123
number += 1
answer = [1, 2, 4]

This works in Python because Python integers can grow very large.

But the point of the problem is to handle the number as digits. In many languages, the integer could be too large for built-in numeric types.

So we should simulate addition directly on the array.

Key Insight

When adding one manually, we start from the rightmost digit.

If the digit is less than 9, we can simply add one and return.

For example:

[1, 2, 3] -> [1, 2, 4]

But if the digit is 9, adding one turns it into 0 and creates a carry.

For example:

[1, 2, 9] -> [1, 3, 0]

The carry continues left while we keep seeing 9.

The only time the array grows is when every digit is 9.

For example:

[9, 9, 9] -> [1, 0, 0, 0]

Algorithm

Scan the array from right to left.

For each index i:

1. If digits[i] < 9, increment it and return the array.
2. Otherwise, set digits[i] = 0 and continue left.

If the loop finishes, then every digit was 9.

Return a new array:

[1] + digits

At that point, digits contains only zeroes.

Correctness

The algorithm processes digits from least significant to most significant, which is exactly how addition with carry works.

If a digit is less than 9, adding one to it creates no carry. All digits to its left remain unchanged, and all digits to its right have already been handled. Returning immediately gives the correct result.

If a digit is 9, adding one changes it to 0 and carries one to the next digit on the left. Setting it to 0 and continuing preserves the correct addition behavior.

If every digit is 9, then each digit becomes 0 and a carry remains after the most significant digit. The only valid result is a leading 1 followed by all zeroes, which the algorithm returns.

Therefore the algorithm returns exactly the original integer plus one.

Complexity

The returned array may have length n + 1 when the input is all 9s.

Implementation

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits

            digits[i] = 0

        return [1] + digits

Code Explanation

We start from the last digit:

for i in range(len(digits) - 1, -1, -1):

If the digit is smaller than 9, no carry continues:

if digits[i] < 9:
    digits[i] += 1
    return digits

If the digit is 9, it becomes 0:

digits[i] = 0

Then the loop continues to the digit on the left.

If the loop finishes, all digits were 9, so we need a new leading 1:

return [1] + digits

Testing

def run_tests():
    s = Solution()

    assert s.plusOne([1, 2, 3]) == [1, 2, 4]
    assert s.plusOne([4, 3, 2, 1]) == [4, 3, 2, 2]
    assert s.plusOne([9]) == [1, 0]
    assert s.plusOne([1, 2, 9]) == [1, 3, 0]
    assert s.plusOne([9, 9, 9]) == [1, 0, 0, 0]
    assert s.plusOne([0]) == [1]

    print("all tests passed")

run_tests()