66. Plus One

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

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Solution:

The ideas is if the last digit is less than 9, we simply increment it by 1 and return.

Otherwise, we set this digit to 0 and decrease the index by 1 and do it again.

When we finish the while loop, we know we have to add one one the beginning.

Therefore, we create a new array with the new length and set the first bit to 1.



Code:

public class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length - 1;
        while (len >= 0) {
            if (digits[len] < 9) {
                digits[len]++;
                return digits;
            }
            else {
                digits[len--] = 0;
            }
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}