Plus One on an array

Given an array representing a integer with each index representing each digit starting from the most significant digit to the least,

add one to the integer and return the output as an array.

For example,

For the input [1,6,7],

The output is [1,6,8]

For the input [9,9],

The output is [1,0,0].

Try out the solution here:

https://leetcode.com/problems/plus-one/

Solution:

A straightforward solution is to add one to the last digit.

If there is any carry over add it to the previous digit and so on until you reach the first digit.

If the sum of the first digit has a carry over value then create a new position in the array and assign it.

A better solution is:

Starting from the end in the array,

Check if each digit is 9 or not.

If it is not 9 just add 1 to that digit and return the output array as there will not be any carry over and we have got the required output.

If the digit is 9 , then make it zero and move to the next digit.

We will add 1 to every other digit which is non 9 and return immediately.

So at the end of the iteration if we have not returned the output then it means all the digits are 9.

Because only if all the digits are 9 , when we add 1 to it we get an output with 1 more digit in it.

In this case we will create a new array with length one more than the input array and assign the first value of the array to 1 and return (by default rest will be zero).

So additional space is required only for the worst case (all 9’s).

Here is the code:

class Solution {
    public int[] plusOne(int[] digits) {
     
       
        
        for(int i=digits.length-1;i>=0;i--){
            
            
            if(digits[i] != 9){
                
                
                digits[i] = digits[i]+1;
                
                return digits;
            }
            
            
            digits[i] = 0;
        }
        
        
        digits = new int[ digits.length + 1];
        
        
        digits[0] = 1;
        
        return digits;
    }
}

Why do we add 1 for any digit at any position which is not 9 ?

This is because if the previous digit was not 9 , we would have already returned the output after adding 1.

Only if it was 9 , we would have reached the current position with a carry over of 1.

We need to add this carry over anyway, so we do the addition of 1 at every position with a non 9 value.

Time complexity:

We traverse through each element so time complexity is O(n) where n is the number of elements.

Space complexity:

Except for the worst case where all digits are 9 (we require O(n + 1) space in this case – equal to O(n) ignoring the constant) , we don’t require any additional memory.

That’s it!