Plus One

Array, Iterative Approach

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 most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

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.

Solutions

The algorithm works by iterating over the array of digits from right to left, which corresponds to moving from the least significant digit to the most significant. It checks each digit to see if it's less than 9.

• If it is, the algorithm simply increments the digit by 1 and immediately returns the result, as no further changes are needed.

• If the digit is 9, it means we need to carry over the increment to the next digit. So, the algorithm sets the current digit to 0 and continues to the next digit.

• If all the digits in the array are 9, it means we need an extra digit for the carry over. In this case, the algorithm adds a 1 at the beginning of the array.

Steps

1. Run loop from end of array.

2. Increment current last number by one and check if it is not equal to 10.

3. If it is false then, return current incremented array.

4. if incremented number is 10 then set it value to 0.

5. Continue till condition evaluated false.

6. Create new array of length one plus of original array.

7. Set first element value 1 reset keep 0 as default and return new array.

public class Solution {
    public int[] PlusOne(int[] digits) {
        
         for(int i = digits.Length - 1; i >= 0; i--){
            if(++digits[i] != 10) return digits;
            digits[i] = 0;
        }
        int [] res = new int[digits.Length + 1];
        
        res[0] = 1;
        return res;
    }
}

Complexity

• Time complexity: O(n)

• Space complexity: O(n)