Problem Description

You have a large integer that is represented as an array of digits. Each element in the array represents a single digit of the number, arranged from most significant digit (leftmost) to least significant digit (rightmost). For example, the array [1, 2, 3] represents the number 123.

Your task is to add 1 to this large integer and return the result as an array of digits in the same format.

Key points to understand:

• The input array represents a valid positive integer with no leading zeros
• You need to handle carry-over when adding 1 causes a digit to become 10
• The output should maintain the same array format as the input

For example:

• Input: [1, 2, 3] → Output: [1, 2, 4] (123 + 1 = 124)
• Input: [9, 9] → Output: [1, 0, 0] (99 + 1 = 100)
• Input: [9] → Output: [1, 0] (9 + 1 = 10)

The solution works by starting from the rightmost digit (least significant), adding 1, and handling any carry-over that propagates to the left. If all digits were 9 (resulting in all becoming 0 after the addition), a new digit 1 is added at the beginning of the array.

Intuition

When we add 1 to a number, we naturally start from the rightmost digit (the ones place). This is exactly how we do addition by hand - we add from right to left and handle carries as we go.

The key insight is that adding 1 can only affect digits in two ways:

1. If a digit is less than 9, we simply increment it and we're done - no carry needed
2. If a digit is 9, it becomes 0 and we need to carry 1 to the next digit on the left

Think about what happens when you add 1 to different numbers:

• 123 + 1 = 124: The last digit 3 becomes 4, no carry needed, we stop
• 129 + 1 = 130: The 9 becomes 0, carry 1 to the 2, making it 3, then stop
• 199 + 1 = 200: The last 9 becomes 0, carry to next 9 which becomes 0, carry to 1 which becomes 2
• 999 + 1 = 1000: All 9s become 0s with continuous carries, and we need an extra digit

This naturally leads to a right-to-left traversal approach. We process each digit, and if after adding 1 (or the carry) the digit becomes 10, we use modulo operation (digit % 10) to get 0 and continue to the next digit. If the digit doesn't become 0 after the operation, there's no more carry and we can return immediately.

The special case occurs when all digits were 9 (like 999). After processing, they all become 0, and we exit the loop. At this point, we need to add a new leading digit 1 to represent the overflow, giving us 1000. This is why we return [1] + digits when we've processed all digits without returning early.

Learn more about Math patterns.

Solution Approach

The implementation uses a simulation approach, processing the digits from right to left to handle the addition and carry propagation.

Here's how the algorithm works step by step:

1. Start from the rightmost digit: We begin our traversal from index n-1 (where n is the length of the array) and move towards index 0. This is achieved using the loop: for i in range(n - 1, -1, -1).

2. Add 1 to the current digit: For each digit at position i, we increment it by 1: digits[i] += 1.

3. Handle overflow with modulo: After adding 1, if the digit becomes 10, we need to convert it to 0 and carry over. This is elegantly handled using: digits[i] %= 10.

   • If digits[i] was 9, after adding 1 it becomes 10, and 10 % 10 = 0
   • If digits[i] was less than 9, the modulo operation keeps it unchanged

4. Check for early termination: If after the modulo operation digits[i] != 0, it means there's no carry to propagate further. We can immediately return the modified array. This optimization prevents unnecessary iterations.

5. Handle the all-9s case: If we complete the loop without returning (meaning all digits were 9 and are now 0), we need to add a leading 1. This is done by returning [1] + digits, which creates a new array with 1 at the beginning followed by all the zeros.

Example walkthrough with [1, 9, 9]:

• i = 2: digits[2] = 9 + 1 = 10, after modulo: digits[2] = 0, continue (carry needed)
• i = 1: digits[1] = 9 + 1 = 10, after modulo: digits[1] = 0, continue (carry needed)
• i = 0: digits[0] = 1 + 1 = 2, after modulo: digits[0] = 2, since 2 != 0, return [2, 0, 0]

Example walkthrough with [9, 9]:

• i = 1: digits[1] = 9 + 1 = 10, after modulo: digits[1] = 0, continue
• i = 0: digits[0] = 9 + 1 = 10, after modulo: digits[0] = 0, continue
• Loop ends, return [1] + [0, 0] = [1, 0, 0]

The time complexity is O(n) in the worst case where we need to traverse all digits, and space complexity is O(1) if we don't count the output array (or O(n) if we need to create a new array for the all-9s case).

Example Walkthrough

Let's walk through the solution with the input [2, 9, 9] to see how the algorithm handles carry propagation:

Initial state: digits = [2, 9, 9], we need to add 1

Step 1 - Start from rightmost digit (index 2):

• Current digit: digits[2] = 9
• Add 1: digits[2] = 9 + 1 = 10
• Apply modulo: digits[2] = 10 % 10 = 0
• Check: digits[2] == 0, so we have a carry, continue to next digit
• Array now: [2, 9, 0]

Step 2 - Move to index 1:

• Current digit: digits[1] = 9
• Add 1 (the carry): digits[1] = 9 + 1 = 10
• Apply modulo: digits[1] = 10 % 10 = 0
• Check: digits[1] == 0, so we have a carry, continue to next digit
• Array now: [2, 0, 0]

Step 3 - Move to index 0:

• Current digit: digits[0] = 2
• Add 1 (the carry): digits[0] = 2 + 1 = 3
• Apply modulo: digits[0] = 3 % 10 = 3
• Check: digits[0] == 3, which is not 0, so no more carry needed
• Return [3, 0, 0] immediately

The final result is [3, 0, 0], which represents 299 + 1 = 300.

Special case example with [9, 9, 9]:

• Index 2: 9 + 1 = 10, modulo gives 0, continue
• Index 1: 9 + 1 = 10, modulo gives 0, continue
• Index 0: 9 + 1 = 10, modulo gives 0, continue
• Loop completes with digits = [0, 0, 0]
• Since we didn't return early, we need to add a leading 1
• Return [1] + [0, 0, 0] = [1, 0, 0, 0]

This represents 999 + 1 = 1000.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array digits. In the worst case, when all digits are 9 (e.g., [9, 9, 9]), the algorithm needs to iterate through all n elements in the array from right to left, setting each to 0 before finally prepending a 1 to create the result. In the best case, when the last digit is not 9, the algorithm only processes one element and returns immediately, giving O(1). However, the worst-case time complexity determines the overall complexity, which is O(n).

Space Complexity: O(1) if we exclude the space used for the output. The algorithm modifies the input array in-place and only uses a constant amount of extra space for the loop variable i and the temporary variable n. The only case where additional space is allocated is when all digits are 9, requiring the creation of a new list [1] + digits of size n + 1. However, following the convention stated in the reference answer where we ignore the space consumption of the answer itself, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting String Conversion Approach

A common pitfall is trying to convert the array to an integer, add 1, then convert back to an array. This approach fails for very large numbers that exceed language integer limits.

Problematic approach:

# This will fail for very large numbers
def plusOne(digits):
    num = int(''.join(map(str, digits)))  # Convert to integer
    num += 1
    return [int(d) for d in str(num)]      # Convert back to array

Why it fails: The problem specifically mentions "large integer" - arrays could represent numbers with hundreds or thousands of digits, far exceeding the maximum integer size in most programming languages.

2. Forgetting to Handle the All-9s Case

Another pitfall is not properly handling when all digits are 9, requiring the array to grow by one element.

Incorrect implementation:

def plusOne(digits):
    carry = 1
    for i in range(len(digits) - 1, -1, -1):
        digits[i] += carry
        if digits[i] == 10:
            digits[i] = 0
            carry = 1
        else:
            carry = 0
            break
    return digits  # Missing the case where we need [1] + digits

Solution: Always check if carry remains after processing all digits. If it does, prepend 1 to the array.

3. Modifying Input Array Without Considering Immutability Requirements

Some implementations might require returning a new array without modifying the input. The provided solution modifies the input array directly.

Better practice for immutability:

def plusOne(digits):
    result = digits.copy()  # Create a copy first
    n = len(result)
  
    for i in range(n - 1, -1, -1):
        result[i] += 1
        result[i] %= 10
        if result[i] != 0:
            return result
  
    return [1] + result

4. Using Complex Carry Logic

Overcomplicating the carry mechanism with additional variables and conditions when the modulo operator handles it elegantly.

Overcomplicated approach:

def plusOne(digits):
    carry = 1
    i = len(digits) - 1
    while i >= 0 and carry == 1:
        total = digits[i] + carry
        carry = total // 10
        digits[i] = total % 10
        i -= 1
    if carry == 1:
        return [1] + digits
    return digits

Why the simple solution is better: The modulo approach with early return is cleaner and easier to understand. The logic digits[i] %= 10 combined with checking if the result is non-zero eliminates the need for explicit carry tracking.