Plus One Problem [LeetCode Top Interview Question Series]

Soultion

public static void main(String[] args) {
    int[] digits = {8,9,9};
    int[] out = plusOne(digits);
    System.out.println(Arrays.toString(out));
}

private static int[] plusOne(int[] digits) {
    for(int i = digits.length-1;i>=0;i--){
        if(digits[i] < 9){
            digits[i] = digits[i] + 1;
            return digits;
        }
        digits[i] = 0;
    }
    // Handling case where all items are 9
    int[] out = new int[digits.length + 1];
    out[0] = 1;
    return out;
}

The solution starts from the rightmost digit of the array and increments it by one. If the digit is less than 9, the increment operation is complete, and we return the resulting array. If the digit is 9, we set it to 0 and continue to the next digit to the left. If all the digits have been processed and we still have not returned the result, it means that the integer has overflowed and we need to add an extra digit in front, which we set to 1.

This solution has a time complexity of O(n), where n is the number of digits in the integer, and a space complexity of O(1) if we use the original array to store the result, or O(n) if we use a new array to store the result.

Step by Step explanation

Here is a step-by-step explanation of the solution to increment a large integer represented as an integer array:

1. Start from the rightmost digit: We start from the rightmost digit because if the increment operation causes a carry, we need to propagate the carry to the left, and starting from the rightmost digit ensures that we process the digits in the correct order.
2. Check if the digit is less than 9: If the digit is less than 9, it means that the increment operation will not cause a carry and we can simply increment the digit and return the resulting array.
3. Set the digit to 0: If the digit is 9, it means that the increment operation will cause a carry, so we set the digit to 0 and continue to the next digit to the left.
4. Repeat steps 2 and 3 for each digit: We repeat steps 2 and 3 for each digit until we either return the result or reach the first digit.
5. Add an extra digit in front: If we reach the first digit and have not returned the result, it means that the integer has overflowed and we need to add an extra digit in front, which we set to 1.

Overall, the solution increments the integer by one, handling the carry operation as needed, and returns the resulting array of digits.