Plus One easy

Problem Statement

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].

Steps to Solve

1. Iterate from the least significant digit: Start from the rightmost digit of the array.
2. Increment the digit: Add 1 to the current digit.
3. Handle carry: If the digit becomes 10, set it to 0 and carry-over 1 to the next digit. Continue this process until there is no carry-over.
4. Handle leading 1: If after the iteration, there's still a carry-over (meaning the original number was all 9s), prepend a 1 to the beginning of the array.

Explanation

The algorithm simulates the manual process of adding 1 to a number. We start from the rightmost digit and add 1. If the sum exceeds 9, we reset the digit to 0 and propagate the carry-over to the next digit. This continues until either we reach the leftmost digit or there's no carry-over left. If a carry-over remains after processing all digits, it implies that we've incremented a number composed entirely of 9s, resulting in a number with an additional leading 1.

Code

def plusOne(digits):
    """
    Increments a large integer represented as an array of digits by one.

    Args:
      digits: A list of integers representing the digits of a large integer.

    Returns:
      A list of integers representing the incremented integer.
    """
    n = len(digits)
    carry = 1  # Initialize carry-over to 1

    for i in range(n - 1, -1, -1):  # Iterate from right to left
        digits[i] += carry
        carry = digits[i] // 10  # Check for carry-over
        digits[i] %= 10  # Update the digit

    if carry:  # If carry remains after processing all digits
        digits.insert(0, carry)  # Add the carry-over as a leading 1

    return digits

Complexity

• Time Complexity: O(n), where n is the number of digits. We iterate through the array at most once.
• Space Complexity: O(1) in most cases. In the worst case (when the input is all 9s), we add a single element to the beginning of the array, resulting in O(1) additional space. We can consider this to be constant space complexity because the additional space is at most a single element.