66 Plus One

66. Plus One

1. Question

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.

2. Implementation

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

        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i] += 1;
                return digits;
            }
            else {
                digits[i] = 0;
            }
        }

        int[] res = new int[n + 1];
        res[0] = 1;
        return res;
     }
}

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)