{x}
blog image

Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith 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 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading 0's.

Solution Explanation: Plus One

The problem asks to increment a large integer represented as an array of digits by one and return the resulting array. The input array digits represents the integer with digits ordered from most significant to least significant.

Approach: Simulation of Addition

The most straightforward approach involves simulating the process of adding 1 to the integer. We iterate through the digits from right to left (least significant to most significant).

  1. Increment the last digit: We add 1 to the last digit (digits[n-1]).

  2. Handle Carry: If the incremented digit is less than 10, we're done; otherwise, we have a carry. We set the digit to 0 (its remainder after dividing by 10) and continue to the next digit to the left.

  3. Propagate Carry: We repeat step 2 for each digit until either we don't have a carry or we've reached the beginning of the array.

  4. Handle Overflow: If after processing all digits, we still have a carry (all digits were 9), it means the result is a number with one more digit. We prepend a 1 to the array.

Code Implementation and Explanation (Python)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            digits[i] += 1
            digits[i] %= 10  #Take the remainder after dividing by 10 (handles carry)
            if digits[i] != 0:
                return digits #No more carry, return the updated digits
        return [1] + digits #Handle overflow (all digits were 9)

The Python code directly implements the steps described above. The %= 10 operation efficiently handles the carry. If the result of adding 1 isn't 10 or greater, the if condition immediately returns, otherwise it continues to the next digit to the left. If the loop completes without finding a non-zero digit, it means all digits were 9, so we prepend a 1.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the number of digits in the input array. We iterate through the array at most once.

  • Space Complexity: O(1) in most cases. We modify the input array in-place. In the overflow case (all 9s), we create a new array of size n+1, which is still considered O(1) because the additional space is constant relative to the input size, not proportional to it.

Code in other Languages

The same logic can be implemented in other languages with minor syntactic differences. (Examples provided in the original response). The core algorithm and complexity remain the same across all languages.