Leetcode: Plus One

This question is asked very commonly on Facebook and Tik Tok. 

Here's the question:

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored in the array. This is supposed to be an easy problem, so I guess it's a good warmup.

Here are the examples:

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

Below, I will enumerate the solution to this problem.

The schoolbook addition with the carry is the best algorithm, so that's what we're actually going to do.

First, we want to start from the end of the array, and if the number is 9, set this number to zero, and set the carry equal to one. The time complexity is O(N). If all the digits are equal to nine, set a zero in front. And that's basically how you solve the problem. Iterate backwards, until you find that one digit is not equal to 9 then add one to it. 

Here's the solution: 

class Solution {

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

        int n = digits.length;

        //go over all the digits

        for(int idx = n - 1; idx >= 0; --idx) {

            if(digits[idx] == 9) digits[idx] = 0;

            else {

                //if number doesn't equal 9 add the least 1 and increment 1 to it. 

                digits[idx]++;

                return digits;

            }

        }

        //else add a 1 to the front or the most significant digit of the number. 

        digits = new int[n + 1];

        digits[0] = 1;

        return digits;

    }

}