LeetCode Problem 66 — Plus One — Algorithm and Java Solution

Photo by Markus Spiske on Unsplash

Hi Friends,

Today we are going to solve a Leetcode problem number 66. Please feel free to read problem description from below link.

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

In given problem , it states that you have a non-empty and non-negative array storing single digit value at each position and most significant bit is stored at head of list.

Now we look at below example , when 1 is added to last digit 3 , it becomes 4 which would be simple to achieve.

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

But problem comes when last digit is 9 where you add 1 , it becomes 2 digit number = 10 which is not allowed in array.

So in that you have keep 0 at unit place and use carry 1 to be added in next digit. For Example

Input: digits = [1,2,9] 
Output: [1,3,0] 

Now in above example , 1 added to 9 is replaced with 0 and carry got added to 2 became 3.

Corner Case:

Everything works fine except where 9 is placed at first position at index 0.In this scenario, you will have to extend array size by 1 to accommodate extra bit. Below is example.

Input: digits = [9,9,9]
Output: [1,0,0,0]

Hope you have understood problem . Now let’s look at algorithm below.

Algorithm

1. Start a while loop starting from last position approaching towards 0 position of array.

while(lastPosition >= 0)

2. Increment last position by 1.

3. If value is less than or equal to 9 , then return digits with updated last value.

if(incrementedValue <=9) // if less than equal to 9 - break and return.
            {
                digits[lastPosition] =  incrementedValue;
                break;
            } 

4. Else if you reach at starting index 0 , then create new array with +1 length and assign 1 to Zeroth index. Finally return new array.

if(lastPosition ==0)
           {
            int[] newDigits = Arrays.copyOf(digits,digits.length+1);
            newDigits[0] = 1;
            return newDigits;
           }

6. For all other cases assign 0 and decrement lastPosition by 1;

7. At End return digits array.

Complete Solution :

class Solution {
    public int[] plusOne(int[] digits) {
        
        if(digits.length == 0)
            return digits;
        
       
        int lastPosition = digits.length-1;
    
        
        // While loop starting from end to start 
        while(lastPosition >= 0)
        {
            int incrementedValue = digits[lastPosition] +1; // Increment last position  value;
            
            if(incrementedValue <=9) // if less than equal to 9 - break and return.
            {
                digits[lastPosition] =  incrementedValue;
                break;
            } 
            else
            {
                //else check if you reached to 0 position of Array. 
                // then increment array size by 1
                // assign 1 to zero index. 
                if(lastPosition ==0)
                {
                    int[] newDigits = Arrays.copyOf(digits,digits.length+1);
                    newDigits[0] = 1;
                    return newDigits;
                }
                else
                {
                    // if lastPosition is somewhere in middle then assign 0 to position and decrement position.
                    digits[lastPosition] = 0;
                    lastPosition--;
                }
                
            }
                 
        }
        
        return digits;
    }
}

Keep learning , Keep Sharing. :)

Originally published at http://learning-madeeasy.blogspot.com.