You are 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 zeros, except for the number 0 itself.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading zeros, except for the number 0 itself.

Solution

The problem asks us to increment a large number, represented as an array of digits, by one. The key is to handle potential carry-overs.

Approach:

  • Iterate through the digits array from right to left (from the least significant digit to the most significant digit).
  • For each digit, add 1 to it.
  • If the digit becomes less than 10 (i.e., no carry-over occurred), we have successfully incremented the number. Return the digits array as is.
  • If the digit becomes 10, set it to 0 (indicating a carry-over) and continue the loop to the next digit to the left.
  • If the loop finishes and there is still a carry-over (this happens when all digits were 9, e.g., [9,9,9] becomes [1,0,0,0]), it means we need to prepend a 1 to the beginning of the array. The simplest way is to create a new array of size n+1, set the first element to 1, and the rest to 0s.
class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        n = len(digits)

        # Iterate from the rightmost digit to the leftmost
        for i in range(n - 1, -1, -1):
            if digits[i] < 9:
                # If the current digit is less than 9, just increment it
                # and return, as no carry-over is needed.
                digits[i] += 1
                return digits
            else:
                # If the current digit is 9, set it to 0 and carry over 1.
                digits[i] = 0
        
        # If we reach here, it means all digits were 9s (e.g., [9,9,9]).
        # We need to prepend a 1 to the array.
        # Example: [9,9] becomes [1,0,0]
        return [1] + digits