Problem statement – Given a non-negative integer in the form of an array of digits, add one to digit array. The digits are stored such that the most significant digit is at the head of the list. Eg. –

A = {1, 3, 5}, answer = {1, 3, 6}

Solution – When an interviewer asks questions like these, he is testing your implementation skills and you ability to discover the corner cases. The solution is simply to add 1 to the last digit and pass on the carry until the first digit. But there are a few cases to handle, like –

• A = {2, 4, 9}, answer = {2, 5, 0}
• A = {9, 9}, answer = {1, 0, 0}
• A = {0, 0, 1, 9}, answer = {2, 0}
• A = {0}, answer = {1}

If we have passed the carry value to the end of the array and we still have carry left, then that would be appended as the new most significant bit. The digit array may be having leading zeroes, you should trim them before proceeding to solve the problem. But don’t blindly trim all leading zeroes, you should also handle the case when we have just a 0.

This is a simple problem to code, if you are aware of all the corner cases. Try it on your own once. 🙂

Code –

public ArrayList<Integer> plusOne(ArrayList<Integer> arr) {
    preprocessInput(arr);
    
    int carry = 1;
    
    for (int i = arr.size() - 1; i >= 0; --i) {
        if (carry == 0) {
            return arr;
        }
        
        int num = arr.get(i);
        
        num++;
        
        arr.set(i, num % 10);
        carry = num / 10;
    }
    
    if (carry == 1) {
        arr.add(0, carry);
    }
    
    return arr;
}

public void preprocessInput(ArrayList<Integer> arr) {
    while (arr.size() > 1) {
        if (arr.get(0) == 0) {
            arr.remove(0);
        } else {
            break;
        }
    }
}

Keep practicing! Happy Coding! 😀