PROBLEM STATEMENT

Given a non-negative number represented as an array of digits,
add 1 to the number ( increment the number represented by the digits ).
The digits are stored such that the most significant digit is at the head of the list.

INPUT

If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

EXTRA NOTES

Q : Can the input have 0’s before the most significant digit. Or in other words, is 0 1 2 3 a valid input?
A : For the purpose of this question, YES

Q : Can the output have 0’s before the most significant digit? Or in other words, is 0 1 2 4 a valid output?
A : For the purpose of this question, NO. Even if the input has zeroes before the most significant digit.

IDEA

What happens when we add a number to the last if it is not a 9. Cool, we can simply add 1 and return the result directly. But the problem arises when we have 9 as last digit.
What happens when we add 1 to 9. Yes We will get a carry 1 and it has to be added with the next digit too.
Ok, that's the case when we have the last digit as 9. What if we have all the digits as 9.
EG: [9, 9, 9]
so when we add 1 to the last digit, it become 0 and we get carry 1.
When we add this carry to the other 9, it become 0 and we get carry 1.
Again we add this carry to the very first 9, it become and we get carry 1.

So the final result will [0, 0, 0] and a carry 1. So we have to add the number to the very beginning and thus we get [1, 0, 0 ,0]. This indicates that our size increases from 3 to 4. So this must also be kept in mind.

ALGORITHM

1. Initialise a varible reminder to store the carry.
2. Precheck the edge case when we have so many 0's at the beginning and it is removed. 3.Traverse the list from the end, then: -> if the last digit = 9, remove it, add 0 and update the reminder = 1. -> if the last digit != 9, remove it, add number+1 and update reminder = 0 and exit from the loop.
3. If we have all 9,still our reminder will be 1.
4. Check if reminder = 1, if yes, add 1 to the very beginning.
5. Return the list.

public class Solution {
    public ArrayList<Integer> plusOne(ArrayList<Integer> A) {
        int reminder = 0;
        // to remove the very first 0
        while (A.size() > 1 && A.get(0) == 0)
            A.remove(0);
        for (int i=A.size()-1; i>=0; i--) {
            int number = A.get(i);
            if (number == 9) {
                A.remove(i);
                A.add(i, 0);
                reminder = 1;
            }
            else {
                A.remove(i);
                A.add(i, number+1);
                reminder = 0;
                break;
            }
        }
        if (reminder == 1) {
            A.add(0, 1);
        }
        return A;
    }
}

Time Complexity: O(lengthOfList)
Space Complexity: O(1)

Github Link: Link