Teaching Kids Programming – Add One to List

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

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

Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Example 3:
Input: digits = [0]
Output: [1]

Enumerate and Carry Over From Least Significant Digit

We add one to the rightmost (least significant digit), then update as long as the carry isn’t zero. The // 10 deletes the rightmost digit where % 10 gets the rightmost digit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1
        c = 0
        x = len(digits) - 1
        while x >= 0:
            digits[x] += c
            c = digits[x] // 10
            digits[x] %= 10
            if c == 0: # no need to continue
                break
            x -= 1
        if c > 0:
            digits.insert(0, c)
        return digits

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1
        c = 0
        x = len(digits) - 1
        while x >= 0:
            digits[x] += c
            c = digits[x] // 10
            digits[x] %= 10
            if c == 0: # no need to continue
                break
            x -= 1
        if c > 0:
            digits.insert(0, c)
        return digits

Another implementation – which we start from the second last digit (and put carry condition)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1
        c = digits[-1] // 10
        digits[-1] %= 10
        x = len(digits) - 2
        while x >= 0 and c >= 0:
            digits[x] += c
            c = digits[x] // 10
            digits[x] %= 10
            x -= 1
        if c > 0:
            digits.insert(0, c)
        return digits

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1
        c = digits[-1] // 10
        digits[-1] %= 10
        x = len(digits) - 2
        while x >= 0 and c >= 0:
            digits[x] += c
            c = digits[x] // 10
            digits[x] %= 10
            x -= 1
        if c > 0:
            digits.insert(0, c)
        return digits

Time complexity is O(N) where N is the length of the array. This algorithm is similar to: Coding Exercise – Plus One C++ – Online Judge

–EOF (The Ultimate Computing & Technology Blog) —