algoadvance

You are given a large integer represented as an 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 integer does not contain any leading zeroes.

Your task is to increment the integer by one and return the resulting array of digits.

Clarifying Questions

Before we proceed, let’s clarify a few things:

1. Input format: Is it guaranteed that the input list digits will not contain any leading zeroes except for the number zero itself?
   • Yes, it is guaranteed.
2. Output format: The output should also be in the form of a list of digits without any leading zeroes?
   • Yes, the output should be in the same format.
3. Constraints: Is there a maximum length for the input list?
   • Generally, no specific constraint on the length apart from typical input size limits in LeetCode problems.

Strategy

1. Traverse from the End: Start from the end of the list and increment the last digit by one.
2. Carry Handling: If the incremented digit is less than 10, we’re done. If it’s 10, set the digit to 0 and propagate the carry to the next significant digit.
3. Extra Digit: If we have a carry left after processing all digits (e.g., from 999 to 1000), we need to insert a 1 at the beginning of the list.

Code

def plusOne(digits):
    # Start from the end of the array
    for i in reversed(range(len(digits))):
        # If the current digit is less than 9, simply increment it by 1 and return the modified list
        if digits[i] < 9:
            digits[i] += 1
            return digits
        # Otherwise, set the current digit to 0
        digits[i] = 0
    
    # If we exit the loop, it means we had a carry out from the most significant digit
    # This means all digits were 9 initially, so we need an extra digit at the beginning
    return [1] + digits

# Example usage:
print(plusOne([1, 2, 3]))  # Output: [1, 2, 4]
print(plusOne([4, 3, 2, 1]))  # Output: [4, 3, 2, 2]
print(plusOne([9]))  # Output: [1, 0]
print(plusOne([9, 9, 9]))  # Output: [1, 0, 0, 0]

Time Complexity

• Time Complexity: O(n), where n is the number of digits in the list. We potentially iterate through all the digits once in the worst case.
• Space Complexity: O(1) for the extra space, although the result array will store the new digits which would also be O(n).

This solution handles the carry propagation effectively and works for the general case when dealing with very large numbers represented as arrays of digits.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?