Plus One easy

Problem Statement

You are given a 0-indexed integer array digits that represents a large integer. The digits are ordered from most significant to least significant in left-to-right order. You need to add one to this large integer. Return the resulting array of digits.

Example 1

Input: digits = [1,2,3] Output: [1,2,4] Explanation: The represented integer in base 10 is 123. Adding one to 123 gives 124.

Example 2

Input: digits = [9] Output: [1,0] Explanation: The represented integer in base 10 is 9. Adding one to 9 gives 10.

Steps

1. Iterate from the least significant digit: We start from the rightmost digit (least significant) and add 1 to it.
2. Handle carry: If adding 1 results in a digit greater than 9, we set the digit to 0 and carry-over 1 to the next digit to the left. We continue this process until there is no carry-over or we reach the most significant digit.
3. Handle carry-over to the most significant digit: If, after iterating through all digits, we still have a carry-over (meaning the original number was all 9s), we need to prepend a new digit 1 to the beginning of the array.

Explanation

The core logic involves simulating addition with carry. We work from right to left because addition works this way – we start with the units place and then propagate any carry to the tens place, hundreds place, and so on. The special case of a carry-over at the most significant digit requires adding a new digit at the beginning of the array.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int[] PlusOne(int[] digits) {
        int n = digits.Length;

        // Iterate from the rightmost digit
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits; // No carry-over, we're done
            } else {
                digits[i] = 0; // Set digit to 0 and carry-over
            }
        }

        // If we reach here, it means there was a carry-over from all 9s
        List<int> result = new List<int>();
        result.Add(1); // Prepend 1
        result.AddRange(digits); // Add the rest of the digits (all 0s)

        return result.ToArray();
    }
}

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 the average case (no extra space used beyond the input array). In the worst case (all 9s), it becomes O(n) because a new array of size n+1 is created. However, this worst-case scenario is still considered linear with respect to the input size.