LeetCode : Plus One

Given a non-empty array of digits representing a non-negative integer, plus 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 contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Approach : To add one to number represented by digits, follow the below steps :

• Parse the given array from end like we do in school addition.
• If the last elements 9, make it 0 and carry = 1.
• For the next iteration check carry and if it adds to 10, do same as step 2.
• After adding carry, make carry = 0 for the next iteration.
• If the vectors add and increase the vector size, append 1 in the beginning.

Approach #1

The solution itself is correct but not very efficient. In this solution, we need to traverse all digits of the array, no matter if there is a carry value. Actually we know that only if the digit is 9, there is a carry value to consider. So one better idea is to plus one at the original digital array. Then we can safely stop the process as long as there is no carry value.

public class Solution {
    public int[] plusOne(int[] digits) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (digits == null || digits.length == 0) {
            int[] temp = {1};
            return temp;
        }
         
        int carry = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (i == digits.length - 1) {
                carry = carry + digits[i] + 1;
            } else {
                carry += digits[i];
            }
            result.add(0, carry % 10);
            carry /= 10;
        }
         
        if (carry == 1) {
            result.add(0, 1);
        }
        int resultArray[] = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
         
        return resultArray;
    }
}

Approach #2

The second solution is smart by not easy to understand at the first glance. Both of the solutions have its pros and cons.

In the first solution, we have to iterate all digits of the array no matter if there exists the carry value. However, it does not modify the original array, which is sometimes preferred in certain cases.

The second solution is neat but modify the original input array. In addition, the second solution is restricted to only plus one problem, whereas the first solution is more general to any adding two numbers problems.

class Solution {
    public int[] plusOne(int[] digits) {
        
        if(digits == null || digits.length == 0){
            int[] temp={1};
            return temp;
        }
        
        int carry=1;
        int i;
        for( i=digits.length-1;i>=0;i--){
            if(digits[i]==9){
                digits[i]=0;
            }
            else{
                carry+=digits[i];
                digits[i]=carry;
                break;
            }
        }
        if(i<0){
            int[] result = new int[digits.length+1];
            result[0]=1;
            return result;
        }else
            return digits;
    }
}