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 = [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:

  1. Iterate from the least significant digit: We start from the rightmost digit (least significant) of the array.
  2. Increment the digit: Add 1 to the current digit.
  3. Handle carry-over: If the incremented digit becomes 10, we set it to 0 and carry-over 1 to the next digit. This process continues until there's no carry-over or we reach the most significant digit.
  4. Handle carry-over to the most significant digit: If after processing all digits, there's still a carry-over (meaning the original number was all 9s), we need to prepend a 1 to the array.
  5. Return the updated array: The updated array represents the incremented integer.

Explanation:

The solution simulates the manual process of adding 1 to a number. We start from the ones place and work our way to the left, handling carry-overs as we go. The loop continues until either there is no carry-over left or we process the most significant digit. If there is a carry-over after processing all digits, it implies the number was all 9s, hence a new digit (1) needs to be added at the beginning.

Code:

function plusOne(digits: number[]): number[] {
    let carry = 1; // Initialize carry-over to 1

    for (let i = digits.length - 1; i >= 0; i--) {
        let sum = digits[i] + carry;
        digits[i] = sum % 10; // Update digit with remainder (0-9)
        carry = Math.floor(sum / 10); // Update carry-over (0 or 1)

        if (carry === 0) {
            break; // No more carry-over, we're done
        }
    }

    if (carry > 0) {
        digits.unshift(carry); // Prepend 1 if there's still carry-over
    }

    return digits;
};

Complexity:

  • 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 worst-case scenario (when the input is all 9s), we add one element to the array, resulting in O(1) space complexity still since the addition is constant.