Plus One easy

Problem Statement

Given a non-empty array of digits representing a non-negative integer, increment the integer by one and return the resulting array of digits.

You must not allocate extra space for the result, but you may modify the input array in place. The digits are stored such that the most significant digit is at the index 0, and each element in the array contains a single digit.

Example 1

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

Example 2

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

Steps

1. Iterate from the least significant digit: Start from the rightmost digit (end of the array).
2. Increment the digit: Add 1 to the current digit.
3. Handle carry: If the digit becomes 10, set it to 0 and carry-over 1 to the next digit (left). This carry-over will be handled in the next iteration.
4. Check for carry at the most significant digit: If after processing all digits, there's still a carry (meaning the number was all 9s initially), we need to add a new digit (1) at the beginning of the array.
5. Return the modified array: The digits array now holds the incremented integer.

Explanation

The solution leverages the concept of carry-over addition. We process the digits from right to left, similar to how we perform addition manually. When a digit plus the carry becomes 10, we reset the digit to 0 and propagate the carry to the next significant digit. This process continues until either a digit doesn't produce a carry or we reach the most significant digit. If a carry remains after processing the most significant digit, we prepend a 1 to the array to accommodate the additional digit.

Code

#include <vector>

std::vector<int> plusOne(std::vector<int>& digits) {
    int n = digits.size();
    for (int i = n - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    // If we reach here, it means all digits were 9s.
    std::vector<int> result(n + 1);
    result[0] = 1;
    return result;
}

Complexity

• Time Complexity: O(n), where n is the number of digits. We iterate through the array at most once.
• Space Complexity: O(1) in-place modification. In the worst case (all 9s), we create a new array of size n+1, but this is still considered constant extra space relative to the input size. If we ignore the output array, then it's O(1).