[LeetCode] 66. Plus One

Table of Contents

Description

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 0’s.

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 \leq digits.length \leq 100$
• $0 \leq digits[i] \leq 9$
• digits does not contain any leading 0’s.

Approach

Use a simple right-to-left increment strategy that updates digits in place and propagates any carry toward more significant positions. The algorithm performs a single backward pass, stopping early when no further carry is needed; only when every digit is 9 does the result grow by one digit.

Solution

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  const MAX_VALUE = 9;

  // Iterate from the rightmost digit to handle addition and carry-over.
  for (let i = digits.length - 1; i >= 0; i--) {
    // If the current digit is not 9, increment it and finish.
    if (digits[i] !== MAX_VALUE) {
      digits[i]++;
      break;
    } else {
      // If the current digit is 9, set it to 0 and carry over.
      digits[i] = 0;
    }
  }

  // If the first digit is 0 (meaning all original digits were 9s),
  // prepend a '1' to the array.
  if (digits[0] === 0) digits.unshift(1);

  return digits;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n)$, where $n$ is the number of digits in the input array. In the worst case, we may need to traverse all digits (e.g., when all digits are 9).

Space Complexity

The space complexity is $O(1)$. We modify the input array in place, and only in the case where all digits are 9 do we create a new array element at the front.