Plus One | Leetcode #66 | Easy

In this post I will discuss the solution to the leetcode problem —Plus One.

Problem:

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

Solution:

This is a very interesting problem. Let’s see what are the possible input cases and how we can handle them. In best case, we will have all the digits less than 9 and hence we will just have to add 1 to the last digit. In worst case, all the digits will be 9 and hence we need an array which can hold one more digit than the input array. Let’s see how the algorithm looks like —

1. Iterate the input array in a reverse direction i.e. from last digit to first digit.
2. If the current digit is 9, we just assign it to 0 i.e. we add 1 to it and handle the carry in next step.
3. If the current digit is not 9, we increment the current digit by 1 and return the input array.
4. After iterating the array completely, if it hasn’t returned yet, that means all the digits in the array were 9 and hence we will need to create a new array with size = input array’s size + 1. Let’s call it result
5. Initialize the first digit of the result array with 1
6. Return the result

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

Hope this helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems