LeetCode Problem 66 — Plus One — Algorithm and Java Solution
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
- 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.