Plus One

Problem

You are given an integer array digits, where each digits[i] is the ith digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.

Return the digits of the given integer after incrementing it by one.

Examples

Example 1:

Input: digits = [1,2,3,4]

Output: [1,2,3,5]

Explanation 1234 + 1 = 1235.

Example 2:

Input: digits = [9,9,9]

Output: [1,0,0,0]

Constraints

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Solution

Use classical algorithm of starting backward and iterating. If we need to carry at the end, then we have a 1 followed by n zeros, and need to create a special vector for that.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        bool carry = true;
        int i = digits.size() - 1;
        while (carry && i >= 0) {
            carry = digits[i] == 9;
            digits[i] = carry ? 0 : digits[i] + 1;
            --i;
        }
        if (carry) {
            std::vector<int> result(digits.size() + 1);
            result[0] = 1;
            return result;
        } else {
            return digits;
        }
    }
};