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.

Example

Input: [1,2,3,4] representing number 1234
Output: [1,2,3,5] representing number 1235

Input: [1,2,3,9] representing number 1239
Output: [1,2,4,0] representing number 1240

Input: [9,9,9,9] representing number 9999
Output: [1,0,0,0,0] representing number 10000

Solution 1: brute force

• Start with the rightmost digit and work to the left, and specify carry value for each move

• If the sum is 10, replace the digit with 0, and set carry be 1

• If the sum less than 10, add current carry to the digit, and set carry be 0

• After looping all digits, if carry = 1, add 1 at the beginning of digits

• time complexity: $O(n)$

def plusOne(digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    carry = 1
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] + carry == 10:
            digits[i] = 0
            carry = 1
        else:
            digits[i] += carry
            carry = 0
    if carry == 1:
        digits = [1] + digits
    return digits

Solution 2: advanced

A fact to notice is when carry = 0, it will stay at 0 always. All the digits on the left of that element keeps the same.

def plusOne(digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] == 9:
            digits[i] = 0
        else:
            digits[i] += 1
            return digits
    return [1] + digits

Solution 3: convert the list to integer

• Convert list to integer

• Plus one to the integer

• Convert back to a list

def plusOne(digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    val = 0
    for i,d in enumerate(digits[::-1]):
        val += d*(10**i)
    val += 1
    return [int(i) for i in str(val)]

Note: this method might cause a overflow problem, i.e. if the integer is too large to store, it will cause an error.