Plus One

You are given a non-empty array of decimal digits representing a non-negative 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. Add one to the integer represented by the array. This is a fundamental operation in many arithmetic algorithms and data structures.

Problem Description

Implement a function that takes an array of digits representing a non-negative integer and returns a new array representing the integer incremented by one.

• Input: A list (or array) of integers, where each integer is a single decimal digit (0-9). The list is guaranteed to be non-empty and represent a non-negative integer. The most significant digit is at the beginning of the list.
• Output: A new list of integers representing the original integer plus one.
• Behavior:
  • If adding one to the last digit does not result in a carry-over, simply increment the last digit.
  • If adding one to the last digit results in a carry-over (i.e., the digit becomes 10), set the last digit to 0 and carry over 1 to the next digit to the left.
  • This carry-over process continues as long as there are carry-overs.
  • If a carry-over occurs at the most significant digit, a new most significant digit (1) needs to be prepended to the array.
• Edge Cases:
  • An array containing only the digit 9.
  • An array containing multiple consecutive 9s.
  • An array representing a large number that requires adding a new digit.

Examples

Example 1:

Input: [1, 2, 3]
Output: [1, 2, 4]
Explanation: The input array represents the number 123. Adding one results in 124.

Example 2:

Input: [4, 3, 2, 1]
Output: [4, 3, 2, 2]
Explanation: The input array represents the number 4321. Adding one results in 4322.

Example 3:

Input: [9]
Output: [1, 0]
Explanation: The input array represents the number 9. Adding one results in 10.

Example 4:

Input: [9, 9, 9]
Output: [1, 0, 0, 0]
Explanation: The input array represents the number 999. Adding one results in 1000.

Constraints

• The length of the input array is between 1 and 100 (inclusive).
• Each element in the input array is an integer between 0 and 9 (inclusive).
• The input array does not contain any leading zeros, except for the number 0 itself (represented as [0]).
• The output array should also not contain leading zeros, unless it represents the number 0.
• The time complexity of your solution should ideally be O(N), where N is the number of digits in the input array.

Notes

Consider how you would handle the "carry" operation when a digit reaches 10. You might want to iterate through the array from right to left. If the most significant digit becomes a carry, you'll need to prepend a new digit to your result.