Plus One easy

Problem Statement

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the 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.

You must not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

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 = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. Incrementing by one gives 4322.

Example 3

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 (the last element 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. Repeat this process until there's no carry.
4. Handle carry at the most significant digit: If after processing all digits, there's still a carry (meaning the original number was of the form 99...9), create a new digit at the beginning of the array (representing the carry) and set the first digit to 1 and the rest to 0.

Explanation

The algorithm simulates the process of adding 1 to a number in base 10. We start from the least significant digit because this is where the addition happens first. The carry-over mechanism ensures that the addition propagates correctly to the more significant digits. The special handling for a carry at the most significant digit addresses the case where adding 1 results in an extra digit.

Code

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        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
        int[] newDigits = new int[n + 1];
        newDigits[0] = 1;
        return newDigits;
    }
}

Complexity

• Time Complexity: O(n), where n is the number of digits. In the worst case (all 9s), we iterate through the array once.
• Space Complexity: O(1) in-place modification. The worst-case scenario creates a new array of size n+1, but this is still considered constant extra space because the size is only increased by a fixed amount (1). If we strictly adhere to the problem's constraint of O(1) extra space, and we are allowed to modify the input array directly, the space complexity is O(1) even in the worst case. However, if we consider the space used by the new array in addition to the input array, it's O(n). The problem statement is somewhat ambiguous on this point.