Plus One

Difficulty: Easy
Topics: Array, Math
Link: https://leetcode.com/problems/plus-one/

Problem Description

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Example 1:


Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:


Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:


Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0’s.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement

We are given an array digits representing a non-negative integer in base-10 positional notation, where digits[0] is the most significant digit (MSD) and digits[digits.length-1] is the least significant digit (LSD). The integer contains no leading zeros except for the trivial representation of zero itself. The objective is to compute the array representation of the integer value (digits → integer) + 1, respecting the same digit-array format constraints.

Formal Definition:
Let $n = \sum_{i=0}^{k-1} \text{digits}[k-1-i] \cdot 10^i$ , where $k = \text{digits.length}$ .
Compute $m = n + 1$ .
Output array $\text{result}$ such that:

$\text{result}[0]$ is the most significant digit of $m$ (non-zero unless $m=0$ ).
$\text{result}[j] = \lfloor m / 10^{(k'-1-j)} \rfloor \bmod 10$ for $j=0,\dots,k'-1$ , where $k'$ is the number of digits in $m$ .

Beginner-Friendly Restatement

Imagine you have a big number written digit-by-digit in a list (like [1,2,3] for one hundred twenty-three). Your task is simply to add 1 to that number, then write the answer as a new list of digits. The tricky part is when the last digit is 9, because then you get a carry-over (just like regular addition). If all digits are 9s (like [9,9]), adding 1 will increase the number of digits (becoming [1,0,0]).

Mathematical Restatement

Given a sequence $(d_0, d_1, \dots, d_{k-1})$ where $d_i \in \{0,\dots,9\}$ and $d_0 \neq 0$ (unless $k=1$ and $d_0=0$ ), let $N = \sum_{i=0}^{k-1} d_i \cdot 10^{k-1-i}$ . Compute $M = N + 1$ . Express $M$ in base-10: $M = \sum_{j=0}^{k'-1} e_j \cdot 10^{k'-1-j}$ with $e_0 \neq 0$ (unless $M=0$ ). Output the sequence $(e_0, e_1, \dots, e_{k'-1})$ .

Constraint Analysis

1 <= digits.length <= 100
- Limitation: The input size is tiny by algorithmic standards (max 100). Even $O(n^2)$ operations (10,000) are trivial. This allows any correct algorithm to pass, but we still seek elegance.
- Edge Cases:
  - Minimum length 1: single-digit numbers (0–9).
  - Maximum length 100: numbers up to $10^{100}-1$ (a googol minus one), far beyond native integer types in most languages (32/64-bit). Thus, we cannot convert the array to a built-in integer type (like int or long) to do the addition — we must operate directly on the array.
0 <= digits[i] <= 9
- Limitation: Each element is a valid decimal digit. No negative digits or values ≥10.
- Edge Cases:
  - Digit 0 appears anywhere except at the front (due to no leading zeros).
  - Digit 9 is special because adding 1 causes a carry.
digits does not contain any leading 0's
- Implication: The most significant digit is non-zero (unless the number is exactly 0, which is represented as [0]).
- Edge Cases:
  - Input [0] is the only legal representation of zero.
  - After increment, if a carry propagates all the way to the front, we may need to insert a new digit (e.g., [9,9] → [1,0,0]). The resulting array will also have no leading zeros.

Hidden Edge Cases Derived from Constraints:

All digits are 9: results in a new array with length increased by 1, first digit 1, rest 0.
Trailing 9s with a non-9 digit before: carry propagates until a digit <9 is found.
No carry: simply increment last digit.
Single-digit input: [0] → [1], [9] → [1,0].
Large array with alternating 9s and non‑9s: carry propagates only through consecutive 9s.

2. Intuition Scaffolding

Analogies

Real-World Metaphor (Car Odometer)
Imagine an old mechanical car odometer with digit wheels. When you drive the last mile, the rightmost wheel turns from 9 to 0 and forces the next wheel to advance by one. If all wheels show 9, they all flip to 0 and a new wheel appears at the left showing 1. Adding one to the integer is exactly this “odometer rollover” operation.
Gaming Analogy (Experience Points Counter)
In RPG games, your experience points (XP) are displayed as a number. When you gain 1 XP, the last digit increases by 1. If it was 9, it becomes 0 and the next digit increases. If your XP was 999, gaining 1 changes it to 1000 — the display adds a new digit. The array is like the XP display digits.
Mathematical Analogy (Carry in Base‑10 Addition)
This is a special case of elementary school addition where you add 1 to a multi‑digit number. The algorithm is: start from the least significant digit, add 1, if the result is 10 set digit to 0 and carry 1 to the next digit, otherwise stop. If carry propagates beyond the most significant digit, insert a new digit 1 at the front.

Common Pitfalls

Converting to integer — Fails for arrays longer than ~19 digits (64‑bit limit) or 10 digits (32‑bit).
Reversing the array — Unnecessary; we can traverse backward.
Using extra array for result in all cases — In‑place modification is possible unless a new digit is needed.
Misunderstanding “no leading zeros” — After increment, [0,9] is invalid input, but [1,0] is valid output.
Overcomplicating with recursion — Iterative solution is simpler and equally efficient.
Not stopping early when carry is absorbed — Once carry is 0, remaining digits stay the same.

3. Approach Encyclopedia

Approach 1: Brute Force (Convert to Integer, Add, Convert Back)

Idea: Parse the array into a big integer (using arbitrary‑precision library or manual string conversion), add 1, then split back into digits.

Pseudocode:

1. Join digits into string
2. Convert string to big integer N
3. N = N + 1
4. Convert N to string S
5. Create array of characters of S, converting each char to int

Complexity:

Time: $O(k)$ for join, $O(k)$ for big‑int increment (assuming big‑int addition is linear in number of digits), $O(k)$ for splitting → $O(k)$ .
Space: $O(k)$ for the string and new array.

Visualization:

digits = [1,2,3]
Join → "123" → int 123
123+1 = 124
124 → "124" → [1,2,4]

Drawback: Requires big‑integer support; not all languages have it natively. Overkill.

Approach 2: Schoolbook Addition with Carry (Optimal)

Idea: Simulate adding 1 from least significant digit, propagating carry as needed.

Step‑by‑Step:

Start from the last digit (index k-1).
Add 1 to that digit.
If the digit becomes 10, set it to 0 and set carry = 1, move to next digit left.
Repeat step 3 until either carry is 0 or we reach beyond the first digit.
If after processing all digits carry is still 1, we need to insert a new digit 1 at the front.

Pseudocode:

carry = 1
for i from k-1 down to 0:
    sum = digits[i] + carry
    if sum == 10:
        digits[i] = 0
        carry = 1
    else:
        digits[i] = sum
        carry = 0
        break
if carry == 1:
    result = [1] + digits   // insert 1 at front
else:
    result = digits

Complexity Proof:

Time: In the worst case (all digits are 9), we loop through all $k$ digits → $O(k)$ .
Best case (last digit <9) we do one iteration → $O(1)$ .
Space: $O(1)$ extra if we modify in‑place except when a new digit is needed ( $O(k)$ for new array). But output array must be new? Problem says “return the resulting array”, so we can modify input if allowed. Typically, we avoid modifying input unless specified. We’ll allocate a new array only when needed (carry to front). Otherwise, we can copy and modify.

Visualization (ASCII Diagram):

Case 1: No carry beyond MSD

digits = [1,2,9]
         i=2: 9+1=10 → set 0, carry=1
         i=1: 2+1=3  → set 3, carry=0, stop
Result: [1,3,0]

Case 2: Carry propagates to front

digits = [9,9]
         i=1: 9+1=10 → 0, carry=1
         i=0: 9+1=10 → 0, carry=1
carry=1 → insert 1 at front
Result: [1,0,0]

4. Code Deep Dive

We implement the schoolbook addition optimally. We’ll write in Python for clarity.

def plusOne(digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    n = len(digits)
    # Traverse from least significant digit
    for i in range(n-1, -1, -1):
        if digits[i] < 9:                    # Why? Because adding 1 won't cause carry.
            digits[i] += 1                   # Increment this digit
            return digits                    # Early exit, no further carry
        else:                                # digits[i] == 9
            digits[i] = 0                    # Set to 0, carry propagates
    # If we finish loop, all digits were 9 -> carry out of most significant digit
    return [1] + digits                      # Insert new most significant digit 1

Line‑by‑Line Annotations:

n = len(digits) — Store length for loop control.
for i in range(n-1, -1, -1): — Iterate from last index to first (step -1).
if digits[i] < 9: — Check if current digit can absorb the carry (since we are effectively adding 1). If digit <9, adding 1 yields ≤9, so no carry generated.
digits[i] += 1 — Perform the increment.
return digits — Return immediately because carry is absorbed. Note: This modifies the input list. If we must preserve input, we should copy first.
else: — Digit is 9.
digits[i] = 0 — Set to 0 and carry propagates (implicitly, carry remains 1 for next iteration).
Loop ends — If we exit loop, every digit was 9 and we’ve set them all to 0.
return [1] + digits — Prepend 1 to the list of zeros (now digits is all zeros). This creates a new list with length n+1.

Edge Case Handling:

Example 1 ([1,2,3]):
i=2 → digit=3<9 → increment to 4 → return [1,2,4].
Example 2 ([4,3,2,1]):
i=3 → digit=1<9 → increment to 2 → return [4,3,2,2].
Example 3 ([9]):
i=0 → digit=9 → set to 0, loop ends → return [1,0].
All nines ([9,9,9]):
Each iteration sets digit to 0, loop finishes → return [1,0,0,0].
Single zero ([0]):
i=0 → digit=0<9 → increment to 1 → return [1].
Trailing nines ([1,9,9]):
i=2 → 9→0, carry continues; i=1 → 9→0, carry continues; i=0 → 1<9 → increment to 2 → return [2,0,0].

5. Complexity War Room

Hardware‑Aware Analysis

Input size ≤100 digits → array fits in a few hundred bytes (4 bytes per int in C, less in Python). Entire process fits in L1 CPU cache (~32KB).
Loop has at most 100 iterations → trivial CPU time (nanoseconds).
Memory allocation: worst case we allocate new list of 101 integers → ~400 bytes in C, in Python overhead higher but still negligible.

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute‑Force (Big‑Int)	$O(k)$	$O(k)$	8/10	❌ Not acceptable (avoids algorithmic insight)
Schoolbook Addition	$O(k)$ worst, $O(1)$ best	$O(1)$ (in‑place) or $O(k)$ if copy	10/10	✅ Ideal (clear, efficient)
Recursive	$O(k)$	$O(k)$ (call stack)	7/10	⚠️ Okay but overcomplicated

Why Schoolbook Addition Wins:

Minimal operations, early exit, no conversion overhead.
Works for any length within given constraints.
Easily explained and proved correct.

6. Pro Mode Extras

Variants Section

Plus Any Number
Problem: Add a given integer n (not just 1) to the digit array.
Solution: Same carry algorithm but add n to LSD and propagate carry while n > 0. Complexity $O(k + \log n)$ .
Two Large Integers Addition
Problem: Given two digit arrays, return their sum.
Solution: Add from LSD, maintain carry. Handle different lengths. Complexity $O(\max(k1, k2))$ .
Plus One with Linked List Digits
Problem: Digits stored in a singly linked list (most significant at head).
Solution: Reverse list, add, reverse back; or use recursion to propagate carry from tail.
Plus One with Binary Digits
Problem: Binary array representing a number, add 1.
Solution: Same algorithm but base‑2: if digit is 1, set to 0 and carry; if 0, set to 1 and stop.

Interview Cheat Sheet

First Mention: “This is essentially a base‑10 addition with carry, starting from the least significant digit.”
Edge Cases: Always test: all 9s, single digit 9, trailing 9s, large array with no carry.
Optimization: Early exit when carry is absorbed saves time.
Space: If interviewer allows input modification, do in‑place. Otherwise, copy once.
Complexity: Time $O(n)$ worst, $O(1)$ best; space $O(1)$ auxiliary, $O(n)$ output.

Final Thought: This problem tests understanding of array traversal, carry propagation, and edge‑case handling — foundational for more complex arithmetic problems (like adding two numbers represented as linked lists).

#66 - Plus One