Plus One

Problem Statement

In this task, you are presented with a number expressed as an array, where each element in the array digits[i] signifies the i-th digit of a large integer. The digit order in the array proceeds from most significant (leftmost) to least significant (rightmost). It's important to notice that the number represented by the array does not start with a zero unless it is zero itself.

Your challenge is to increment this integer by one and produce the updated number as a returned array of digits. The key difficulty lies in handling the carry that results from adding one to a digit especially when this results in a change in the number of digits (e.g., from 999 to 1000).

Examples

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.

Approach and Intuition

Our goal is to simulate the process of addition as done typically on paper, starting from the least significant digit (rightmost) and working our way to the most significant digit (leftmost), while taking care of carries.

1. Start iterating the digits array from the last element (rightmost digit) since we are incrementing the number by one.

   • If the rightmost digit is less than 9, simply increment this digit and return the array.
   • If the digit is 9, this will result in a carry that needs to be propagated to the next significant digit (to the left).

2. Continue with the previous step's iterative process toward the left:

   • If the current digit is less than 9, increment it and break the loop. The process is then complete.
   • If the current digit is 9, set this digit to 0 and continue to the next significant digit to manage the carry.

3. Edge Case Resolution:

   • If the leftmost digit also results in a carry (like turning from 9 to 10), this means all digits in the array were 9.
   • Hence, after the loop, the array will comprise all zeros. Therefore, prepend a 1 at the beginning to accommodate the newest carryover (indicative of the fact that a power of 10 has been reached).

This approach operates directly on the input array, ensuring that both space and time efficiency are maintained, fitting comfortably within the given constraints.

Solutions

class Solution {
public:
    vector<int> incrementVector(vector<int>& numbers) {
        int length = numbers.size();
        for (int index = length - 1; index >= 0; --index) {
            if (numbers[index] == 9) {
                numbers[index] = 0;
            } else {
                numbers[index]++;
                return numbers;
            }
        }
        numbers.insert(numbers.begin(), 1);
        return numbers;
    }
};