Problem Statement

You are given a non-empty array of digits representing a non-negative integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit. The task is to add one to the integer.

Examples:

1. Example 1:

   • Input: [1, 2, 3]
   • Output: [1, 2, 4]
   • Explanation: The number is 123. Adding one results in 124.

2. Example 2:

   • Input: [4, 3, 2, 1]
   • Output: [4, 3, 2, 2]
   • Explanation: The number is 4321. Adding one results in 4322.

3. Example 3:

   • Input: [9, 9, 9]
   • Output: [1, 0, 0, 0]
   • Explanation: The number is 999. Adding one results in 1000, where the length of the array increases.

Constraints:

• The array is non-empty.
• Each element in the array is a single digit in the range 0-9.
• The integer does not have any leading zeros (except for the number 0 itself).

Hints Before Solving

• Hint 1: Start from the least significant digit (i.e., the rightmost element of the array) and simulate the addition process.
• Hint 2: Consider what happens when you add one to a digit that is 9. How do you handle the carry?
• Hint 3: Think about what to do when the entire array consists of 9’s.

Approach 1: Brute Force Simulation

Explanation:

• Idea: Simulate the addition manually by iterating from the end of the array to the beginning.
• Process:
  1. Traverse the array from the last element.
  2. If the current digit is less than 9, increment it by one and return the result immediately.
  3. If the current digit is 9, set it to 0 and move to the next digit (carry over).
  4. If you exit the loop and still have a carry (i.e., all digits were 9), insert a 1 at the beginning.

Visual Walkthrough:

• For [1, 2, 3]:
  • Start with the last digit 3: 3 + 1 = 4 → Result: [1, 2, 4]
• For [9, 9, 9]:
  • Last digit: 9 + 1 = 10 → set to 0, carry 1.
  • Second digit: 9 + 1 = 10 → set to 0, carry 1.
  • First digit: 9 + 1 = 10 → set to 0, carry 1.
  • Carry remains → Prepend 1 → Result: [1, 0, 0, 0].

Approach 2: Optimal In-Place Modification

Explanation:

• Idea: Use the same simulation as in the brute force approach but optimize by stopping early when no further carry is needed.
• Process:
  1. Iterate from the end of the array.
  2. If a digit is not 9, simply increment it and return the array immediately.
  3. If the digit is 9, set it to 0 and continue.
  4. After the loop, if no digit could handle the addition without carry (i.e., all were 9), create a new array with a 1 followed by zeros.

Complexity Analysis:

• Time Complexity: O(n) in the worst case (where n is the number of digits), as you might need to process each digit.
• Space Complexity: O(1) extra space if the result is stored in the input array. In the worst case (all digits are 9), a new array of size n+1 is created.

Detailed Step-by-Step Walkthrough

1. Initialize a pointer at the last index of the array.
2. Iterate backwards:
   • If the digit < 9:
     • Increment the digit by 1.
     • Stop processing: No carry exists.
   • If the digit == 9:
     • Set the digit to 0 (because 9+1 gives 10, and 10 mod 10 is 0).
     • Continue the loop with a carry.
3. Post loop check:
   • If you finish the loop (i.e., all digits were processed), it means you had a carry that extended beyond the most significant digit. Prepend 1 to the array.
4. Return the modified array.

Code Implementation

Python Code