LeetCode 66: Plus One — Simple Explanation with Carry Logic (Java)

Difficulty: Easy

Topics: Array, Math

Platform: Leetcode

Problem Statement

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.

Problem Statement Simplified

Check the last digit, add 1, then return

Mistakes and Learning

Do not turn the array into number.
Only check/change last digit.
Look out for rare cases (ex:[9,9,9,…]

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].

Key Insight

Addition starts from the last digit
If digit < 9 → just increment and stop
If digit = 9 → set to 0 and carry forward

Algorithm

1. Initialize a for loop with i starting from last digit and i decrement at each loop.
2. Check if the digit[i] is less than 9
3. If less than 9, then increment (digit[i]++). return digit.
4. end if.
5. then digit[i]=0.
6. end for loop
7. Initialize an array with digits.length+1.
8. Assign the first digit of new array as 1.
9. return the new array.

Algorithm in simple words

First, initialize a for loop that will start from the end of the array and check if that digit is less than 9, if yes then just increment that digit by 1 and return it, SIMPLE ! (ex: suppose the digits array is [4,2,3,2] check the last digit, it is less than 9 , which is 2. So when we increment 2 the final result will be [4,2,3,3], that is the final output).

Suppose the last digit is 9 then make it 0 and then go to the second last digit and check in the if statment. if it is less than 9 then increment by 1 then return. (ex : suppose the digits array iss [4,3,2,9] check if less than 9, NO. Then digitsi will become 0 the array will be [4,3,2,0], i decrease then check for the second last digit (here it is 2) it is less than 9 so increamnet by 1 then return so the final result will be [4,3,3,0]).

Suppose the entire is 9 ie the array is [9,9,9] then we will initialize a new array increment the array length by 1, and make the first digit of the array 1.

Java code

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

        int[] newDigits = new int[digits.length + 1];
        newDigits[0] = 1;
        return newDigits;
    }
}

Time & Space Complexity

Time Complexity: O(n)

Space Complexity: O(1) (except when new array is created)