Coding

Leetcode Plus One solution

0
(0)

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0‘s.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading 0‘s.

Solution

The way I thought I would approach this problem is the way we used to do additions in elementary school. Add the 1 to last digit, then carry over and add carry to next to last digit and so on. If the array represents a number like 9 or 99 or 999 and so on then the result array will be one element longer (it will be 10, 100 or 1000 and so on).

Below is Java code for the same. In order to make it more efficient, as soon I get the number which is less than 10 after carry, I return the array. And in special case where the input number will be 9 or 99 or 999 and so on, the result would be simply an array which is one larger than size of input array and would have first element as 1.

class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 0;
        int len = digits.length;
        int num = 0;
        for (int i=0; i<len; i++) {
             num = digits[len-i-1] +  (i==0 ? 1 : carry);                         
             digits[len-i-1] = num%10;
             if (num<10) return digits;
             carry = num/10;
        }
        
        int []nums = new int[digits.length+1];
        nums[0] = 1;
        return nums;
    }
}

Below is the efficiency.

Lessons Learnt

  • Sometimes I see people submitting the solutions which are very succinct (may be the solution is just in one or two lines) but very difficult to understand. Remember it is not a competition like in how less code you can solve the problem. if your code is not understandable by someone, unless he/she reads it 10 times, it is pure shit. This is where a lot of competitive programmers fail during interviews at top notch companies despite solving the problem correctly.
  • When you solve a problem, there will be times where first solution will not be most optimal solution. Think of ways how you can optimize and improve it. That is a skill that will take you long way during interviews as well as actual job.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?