Plus One

Question (LC.66)

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

Assumptions: 1. do not contain any leading zero 2. the most significant digit is at the head of the list

Example

I: [1, 2, 3]
O: [1, 2, 4]
I: [9, 9, 9]
O: [1, 0, 0, 0]

Analysis

Easy array/math are popular warm up questions. Practice speed and bug free.

Brute Force Approach:

linear scan the array from right to left
keep track of a carry
check if (carry == 1) in the end
then create a new array with size + 1

Code w/ side effects

/**
 * The heart of this problem is carry. Need a new array when all 9s.
 */
public int[] plusOne(int[] digits) {
    for (int rp = digits.length - 1; rp >=0; rp--) {
        if (digits[rp] < 9) {
            digits[rp]++;
            return digits;
        } else {
            digits[rp] = 0;
        }
    }

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

Code w/o side effects

public int[] plusOne(int[] digits) {
    int n = digits.length;
    int[] result = new int[n];
    int carry = 1;
    int i;

    for (i = n - 1; i >= 0; i--) {
        result[i] = (digits[i] + carry) % 10;
        carry = (digits[i] + carry) / 10;
    }

    // corner case which requires an extra digit
    if (carry == 1) {
        int[] extra = new int[n + 1];
        extra[0] = 1;
        return extra;
    }

    return result;
}