Problem Statement in English

You’re given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Return the resulting array of digits after adding $1$ to the large integer.

Approach

We can either convert the array of digits to an integer, add 1, and then convert it back to an array of digits. However, this approach is not efficient for very large integers.

The other approach is to iterate through the array from the last digit to the first, adding 1 and handling any carry that results from the addition. If we reach the most significant digit and still have a carry, we can simply add $1$ at the front of the array.

If we don’t encounter a carry, we can return the modified array as is, and skip iterating any further since the rest is going to be unchanged.

And we’re done!

Solution in Python

  • Hacky

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        return list(map(int, str(int("".join(map(str, digits))) + 1)))
  • Without hacks

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:

        for i in range(len(digits) - 1, -1, -1):

            if digits[i] + 1 != 10:
                digits[i] += 1
                return digits
            
            digits[i] = 0

            if i == 0:
                return [1] + digits

Complexity

  • Time: $O(n)$

  • Space: $O(1)$

And we are done.