Plus One

• LeetCode: Plus One

• Problem:

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.

• Analysis:

[1, 2, 3] + 1 => [1, 2, 4]

[9, 9, 9] + 1 => [1, 0, 0, 0]

Decare carry bit is 1 and add each bits until carry is 0.

• Code - Java:

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        int carry = 1;
        for (int i = len - 1; i >= 0; i--) {
            int value = digits[i] + carry;
            digits[i] = value % 10;
            carry = value / 10;
        }
        if (carry == 0) {
            return digits;
        }
        int[] result = new int[len + 1];
        result[0] = 1;
        for (int i = 1; i <= len; i++) {
            result[i] = digits[i - 1];
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int len = digits.size();
        int carry = 1;
        for (int i = len - 1; i >= 0; i--) {
            int value = digits[i] + carry;
            digits[i] = value % 10;
            carry = value / 10;
        }
        if (carry == 0) {
            return digits;
        }
        vector<int> result(len + 1, 0);
        result[0] = 1;
        for (int i = 1; i <= len; i++) {
            result[i] = digits[i - 1];
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        digitsLen, carry = len(digits), 1
        for i in range(digitsLen - 1, -1, -1):
            value = digits[i] + carry
            digits[i] = value % 10
            carry = value / 10
        if carry == 0:
            return digits
        result = [0 for i in range((digitsLen + 1))]
        result[0] = 1
        for i in range(1, (digitsLen + 1)):
            result[i] = digits[i - 1]
        return result

• Time Complexity: O(N), N is the length of digits array

• Space Complexity: O(N), N is the length of return array