Leetcode 66: Plus one - Cse Nerd Leetcode Detailed Solutions

Category: Easy

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.

“Plus one” problem on Leetcode

Examples

Example 1:

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

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.

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]

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

Solution Approach

In this problem called “plus one”, we are given an array with each element of the array having one number between 0-9. That is, an array element is a one-digit number and we have to consider the array as a whole and add 1 to that number.

The problem looks very intuitive. We still have to look at all the possible edge cases when coming up with the solution. The main thing that we have to consider here is the concept of a ‘carry’ if in case 9 is present at the very end of the array. There can also be a possibility that the array may have all digits as 9. In that case, we have to increase the size of the array and append 1 at the beginning.

As the summation starts from the right to left, we have to follow the same way we add one to the rightmost element. Hence, we have to keep propagating the carry when required. We will have to traverse the problem only once hence the time complexity is O(n). The space complexity is O(1) if any one digit of the array is not 9 in the array otherwise, it becomes O(n+1).

Coming to the code to this problem, we straight away start looping over the element from right to left. Therefore, if any element plus one is less than 9 then we return the answer as an array that has been updated. Otherwise, we change that particular element to 0. In the end, if all the elements are 9 we return a new array whose length is one greater than the previous array and it has 1 at the 0th index, and the rest of the indexes contains 0. We return this new array at the end as the answer.

Solution code

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

class Solution {

public int[] plusOne(int[] digits) {

for(int i = digits.length - 1; i >= 0; i--){

if (digits[i]++ < 9) return digits;

digits[i] = 0;

}

int[] result = new int[digits.length + 1];

result[0] = 1;

return result;

}

For more Leetcode detailed solutions go to Leetcode Detailed Solutions.

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page. I will surely respond to each one of your comments. Happy Leetcoding 🙂