Plus One - Leetcode Solution

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]

Approach:

We start from the last element in the given array and from there we check if adding 1 to the current element will result in a carry. If it does, we set the current element to 0 and move to the previous element, and repeat the process. If we reach the first element and it results in a carry, we add an extra element with 1 as its value, and that becomes the new most significant digit.

Algorithm:

1. Initialize a variable carry to 1
2. Loop from last index of the array to first index: a. Add the current digit to carry. b. If carry is equal to 10, then set carry to 1 and set current digit to 0 else set carry to 0 and break from loop
3. If carry is still 1, create a new array of length n+1, where n is the length of the input array. Set the first element in the new array to 1 and copy the remaining elements from the input array to the new array starting from 2nd position. Else, copy the modified input array to a new array and return it.

Solution:

class Solution { public int[] plusOne(int[] digits) { int n = digits.length; int carry = 1;

    for(int i=n-1; i>=0; i--) {
        int sum = digits[i]+carry;
        if(sum == 10) {
            carry = 1;
            digits[i] = 0;
        }
        else {
            carry = 0;
            digits[i] = sum;
            break;
        }
    }
    
    if(carry == 1) {
        int[] result = new int[n+1];
        result[0] = 1;
        for(int i=1; i<result.length; i++) {
            result[i] = digits[i-1];
        }
        return result;
    }
    else {
        return digits;
    }
}

}

Time Complexity: O(n), where n is the length of the input array.

Space Complexity: O(n), where n is the length of the input array, in case an extra element needs to be added to the array.

1