LeetCode: Plus One Solution

Okay fellas,

Let's get on to some coding problems now!!

Problem Statement:

You are given a large integer represented as an integer array digits, where each digits[i] is the ith 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.

Approach:

• Convert to string, then to number, then add one to the resulting converted number and then again do the inverse conversion. Problem? The test cases have few input numbers in the array which are of BigInteger data type (which means it is greater than Long), now BigInteger does not support .parseInt() method and hence, this approach will fail for these test cases.

Important thing to note here is that the result array size is dynamic, which means that, if we have a last element in the array which is 9, then a carry has to be taken.
Now, this carry will increase the array size and hence we have to think something around using a dynamic array and we all know that a dynamic array best friend is an ArrayList, so let's use it :')

• Using ArrayList: //Base case If there are no elements in the passed array, then return a temporary array which has an element {1}.

`class Solution {
public int[] plusOne(int[] digits) {
ArrayList result = new ArrayList();
if(digits == null || digits.length == 0){
int[] temp = {1};
return temp;
}

// What the heck*1?

    int carry = 0;
    for(int i= digits.length -1; i>=0; i--){
        if(i == digits.length-1){
            carry = carry + digits[i] + 1;
        }
        else
            carry = carry + digits[i];

// What the heck*2?

        result.add(0, carry%10);
        carry = carry /10;

    }
    if(carry == 1){
        result.add(0,1);
    }

//What the heck*3?
int[] resultArray = new int[result.size()];
for(int i=0; i<result.size(); i++){
resultArray[i] = result.get(i);
}
return resultArray;
}
}`

Explaining the hecks*i:

Heck1:
We are traversing our array "digits" from the end, because remember that we have to add 1 at the LSB and also, what if, we have a number 9, at LSB? Then we have to make another variable called "carry" which will hold our carried integer.
Now, what our first "if" is doing is, that it is taking up the last element of the array and it will run only one time,
It is calculating the carry (if any) and adding it to itself.

Heck2:
Remember, the add operation of ArrayList DO NOT replace the value specified at a certain index, rather it just adds it there and shifts the old element to right.
Thus, we will keep on adding carry, at the index position 0, that way, at the end, we will have our first element from digits array at the first index of result arrayList.
Also, for reference;
a%b == a modulus b == gives the REMAINDER
Ex: 32%10 = 2
Whereas,
a/b == gives the QUOTIENT
Ex: 32/10 = 3

We very commonly use "/" operation to take out a certain value at the "1x"th position where x can be 0, 00, 000, 0000, anything.

Heck3:
Because we want to return the result in the array format, hence we are creating a new array called resultArray[] which has the same length as of ArrayList result and then, we are just populating the values in this result[] array.

That's pretty much all for this problem. :)