Leetcode 66: Plus One

1. Problem Statement (Simple Explanation)

You’re given a non-negative integer represented as an array digit:

• digits[i] is the i-th digit (most significant at index 0).

• No leading zeros (unless the number is 0 itself, e.g., [0]).

You must:

• Increment this integer by 1.

• Return the resulting number as a new array of digits.

2. Examples

Example 1:

Input: digits = [1,2,3]

Integer = 123 → 123 + 1 = 124 → [1,2,4].

Output: [1,2,4]

Example 2:

Input: digits = [4,3,2,1]

Integer = 4321 → 4321 + 1 = 4322 → [4,3,2,2].

Output: [4,3,2,2]

Example 3:

Input: digits = [9]

Integer = 9 → 9 + 1 = 10 → [1,0].

Output: [1,0]

3. Approach – Simulate Addition with Carry (O(n))

We simulate adding 1 to the number:

1. Start from the last digit (least significant).

2. Add 1:

• If result < 10:

• Set the digit and return immediately (no further carry).

• If result == 10:

• Set this digit to 0 and propagate a carry to the next digit to the left.

3. Continue moving left while we have carried:

• For each digit + carry:

• If it becomes 10 → set to 0 and carry continues.

• Otherwise, set digit and stop.

4. If we finish the loop and still have a carry (e.g., [9,9,9] → [0,0,0] + carry):

• Need to add a new most-significant digit 1 at the beginning:

• e.g., [9,9] → [1,0,0].

We can do a small optimization:

• Since we are adding exactly 1.

• the first digit from the end that is not 9 gets incremented, and all digits to its right become 0.

• If all digits are 9, we return a new array of length n+1 with 1 followed by n zeros.

Pseudo-code:

Complexity:

Let n = digits.length:

• Time: O(n) (scan at most once from right to left)

• Space: O(1) extra if we can reuse the input array, or O(n) for the new array (required output).

4. Java code

5. C code

(Note: LeetCode C interface typically allows returning either the modified input or a new array.

If you return digits directly, ensure it’s allowed; or always allocate new.)

6. C++ code

7. Python code

8. JavaScript code