Plus One to Array

Problem Statement

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

Your task is to increment the large integer by 1 and return the resulting array of digits.

Examples

Example 1:

Input: digits = [1, 2, 3]
Output: [1, 2, 4]

Explanation:
The array represents the integer 123. Incrementing by one gives 124, so the output is [1, 2, 4].

Example 2:

Input: digits = [9]
Output: [1, 0]

Explanation:
The array represents the integer 9. Incrementing by one gives 10, so the output is [1, 0].

Different Approach

1️⃣ Traverse from Right to Left

Intuition:

The simplest approach is to mimic how addition works when adding 1 to the last digit and handling carries, just like how we add numbers manually.

Steps:

1. Start from the least significant digit (rightmost).
2. If the digit is less than 9, increment it by 1 and return the updated array.
3. If the digit is 9, set it to 0 and continue to the next digit (carry over).
4. If we finish traversing all digits (e.g., for input [9, 9, 9]), we need to add an extra 1 at the beginning.

Dry Run:

Example 1:

digits = [9, 9, 9]

1. Start from the last digit (9).
2. digits[2] = 9, so set it to 0 and carry over.
3. Move to the next digit: digits[1] = 9, set it to 0 and carry over.
4. Move to the next digit: digits[0] = 9, set it to 0 and carry over.
5. Now, add a 1 at the beginning of the array: [1, 0, 0, 0].
6. Return the result.

Example 2:

digits = [1, 2, 3]

1. Start from the last digit (3).
2. digits[2] = 3 is less than 9, so increment it by 1, making the array [1, 2, 4].
3. Return the result.

Code:

#include <iostream>
#include <vector>
using namespace std;

vector<int> plusOne(vector<int>& digits) {
    int n = digits.size();
    
    // Traverse from the last digit to the first
    for (int i = n - 1; i >= 0; i--) {
        // If the current digit is less than 9, increment it and return
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        // If the digit is 9, set it to 0 and continue (carry to the next digit)
        digits[i] = 0;
    }
    
    // If all digits were 9, we need to add a leading 1
    digits.insert(digits.begin(), 1);
    return digits;
}

int main() {
    vector<int> digits = {9, 9, 9};
    vector<int> result = plusOne(digits);
    
    cout << "Result: ";
    for (int digit : result) {
        cout << digit << " ";  // Output should be [1, 0, 0, 0]
    }
    cout << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the number of digits in the array. In the worst case, we may need to traverse all the digits (e.g., for input [9, 9, 9]).
• Space Complexity: O(1) if we ignore the space required for the input and output arrays. If we add a new digit (as in the case of all 9's), the space complexity becomes O(n).