Plus One

The Plus One problem looks deceptively simple—just add one to an integer. But in coding interviews, integers may not fit in standard numeric types, and you’re given the digits in an array instead of working with a number directly. This forces you to think about digit-by-digit arithmetic, carry propagation, and edge cases like overflow.

It’s a classic warm-up problem that tests your understanding of how numbers work at the array level.

Problem

You are given an array of digits, digits, where each element represents a single digit of a non-negative integer. The most significant digit is at the beginning of the array.

Your task:

Add one to this integer and return the resulting array of digits.

Rules:

• The digits contain no leading zeros, except the number 0 itself.
• Each element in digits is between 0 and 9.
• If adding one creates a carry that extends past the most significant digit, you must expand the array.

Example

Input:

digits = [1, 2, 3]

Output:

[1, 2, 4]

Explanation: 123 + 1 = 124.

Input:

digits = [9, 9, 9]

Output:

[1, 0, 0, 0]

Explanation: The number rolls over because 999 + 1 = 1000.

Solution

This problem ultimately simulates the addition you learned in grade school: start from the least significant digit and propagate carries to the left.

Digit arrays make this process mechanical and predictable:

• Add one to the last digit.
• If it becomes 10, set it to 0 and carry 1 to the previous digit.
• Continue until you no longer have a carry.
• If the carry reaches past the leftmost digit, insert a 1 at the beginning.

Key idea

The entire solution runs in \( O(n) \) time, scanning the array from right to left. Most cases end quickly:

• If the last digit is not 9, you simply add one and return.
• Only when the array ends with one or more 9s do you propagate a carry.

Why this approach works

• You are guaranteed each digit is a single decimal digit, so overflow rules are simple.
• Carry handling is isolated and predictable.
• You never convert the digits into an actual integer, which avoids overflow issues in languages with fixed-size numeric types.

Algorithm outline

1. Start from the last index i = len(digits) - 1.
2. Add one to digits[i].
3. If it becomes 10, set it to 0 and move left to i - 1.
4. Continue until:
   • You find a digit that is not 9, or
   • You run out of digits.
5. If you finish the loop with a carry, insert 1 at the start of the list.
6. Return digits.

Sample implementation (Python)

Alternative solution: converting to an integer

In Python, you could convert digits to an integer, add one, and split the result—but:

• It doesn’t generalize well to languages with integer overflow.
• It ignores the spirit of the problem, which is testing your ability to simulate arithmetic manually.

Interviewers strongly prefer the digit-by-digit approach.

Interview insight

The Plus One problem appears frequently in interviews because it tests:

• Your ability to reason through carry propagation
• Your understanding of digit array representations
• Edge cases involving all-nines inputs
• Clean iteration from right to left

It’s one of the simplest examples of handling addition manually, and it sets the foundation for more complex problems like adding two numbers represented as linked lists or large-integer arithmetic.