3.12 Plus One

3.12.1 Problem Metadata

3.12.2 Description

You are given a large integer represented as an integer array digits, where each digits[i] is the \(i^{th}\) 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 zeros.

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

3.12.3 Examples

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124.
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.
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9. Incrementing by one gives 9 + 1 = 10.

3.12.4 Constraints

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

3.12.5 Solution - Carry Propagation

3.12.5.1 Walkthrough

Traverse the array from right to left. Add 1 to the last digit (treating it as the initial carry). For each digit, compute the new carry as digit / 10 and update the digit as digit % 10. If carry remains non-zero after the loop (all digits were 9), prepend 1 to the result array.

3.12.5.2 Analysis

  • Time Complexity: O(n) — single right-to-left pass
  • Space Complexity: O(n) — result array (O(1) extra work; new array only allocated once)

3.12.5.3 Implementation Steps

  1. Initialize carry = 0 and one = 1.
  2. Iterate from index length - 1 down to 0.
  3. At the last index, add one to the digit; at all other indices add carry.
  4. Compute new carry = tempDigit / 10 and store tempDigit % 10 back.
  5. After the loop, if carry == 0, copy digits to result; otherwise prepend carry as a new leading digit.

3.12.5.4 Code - Java

public int[] plusOne(int[] digits) {
    int carry = 0;
    int one = 1;

    for(int i = digits.length - 1; i >= 0; i--) {
        int tempDigit = digits[i];
        if(i == digits.length - 1) {
            tempDigit += one;
        } else {
            tempDigit += carry;
        }
        carry = tempDigit / 10;
        digits[i] = tempDigit % 10;
    }

    int[] result;

    if(carry == 0) {
        result = new int[digits.length];
        System.arraycopy(digits, 0, result, 0, digits.length);
    } else {
        //construct new array with leading 1
        result = new int[digits.length + 1];
        System.arraycopy(digits, 0, result, 1, digits.length);
        result[0] = carry;
    }

    return result;
}

3.12.5.5 Code - Go

func plusOne(digits []int) []int {
    carry := 0
    one := 1
    length := len(digits)

    for i := length - 1; i >= 0; i-- {
        tempDigit := digits[i]
        if i == length-1 {
            tempDigit += one
        } else {
            tempDigit += carry
        }
        carry = tempDigit / 10
        digits[i] = tempDigit % 10
    }

    if carry == 0 {
        return digits
    }

    //construct new array with leading 1
    return append([]int{carry}, digits...)
}