Plus One

Plus One looks like a warm-up. Just add one to a number, right? But the number is stored as separate digits in an array. That small twist is the whole point. The interviewer wants to see if you handle the carry cleanly, especially the tricky case where every digit is a nine.

🎯 The Problem

You get a number stored as digits and you have to add one to it. Here are the rules.

• Each box in the array holds one digit.
• The most important digit comes first.
• Add one to the whole number and return the new digits.

A carry is the extra one that moves to the next digit when a digit goes past nine. For example, 9 + 1 gives 10. The right digit becomes 0 and a 1 carries to the left.

Let us say the array is [1, 2, 3]. That is the number 123. Add one and you get 124. So the answer is [1, 2, 4].

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

Explanation: 123 + 1 = 124

The hard case is something like [9, 9, 9]. That is 999. Add one and you get 1000. So the array grows by one box. You have to handle that growth.

Here is a picture of the easy case and the hard case side by side.

🐢 Approach 1: Turn It Into a Number (Brute Force)

The idea in one line: glue the digits into one real number, add one, then split it back.

The idea:

• Walk the array and build the integer 123.
• Add one to get 124.
• Split it back into digits.

Why it is weak:

• Interview inputs can be hundreds of digits long.
• A normal integer cannot hold a number that big. It overflows.
• Overflow means the value is too large for the variable, so it wraps around and becomes wrong.
• Python hides this because its integers grow without limit. But C, C++, and Java break. So it is not safe in general.

Here is the conversion code for that idea:

def plus_one(digits):
    value = int("".join(str(digit) for digit in digits))
    value += 1
    return [int(ch) for ch in str(value)]


print(plus_one([1, 2, 9]))

⚡ Approach 2: One Backward Pass With Carry (Best)

The idea in one line: add one to the last digit and walk left, carrying nines, exactly like adding on paper.

How it works:

• Start at the rightmost digit.
• If it is less than nine, add one and stop. No carry needed.
• If it is a nine, set it to zero and carry one to the left.
• Keep walking left as long as you keep hitting nines.

The all-nines case:

• If you walk past the left edge and still carry, every digit was a nine.
• Like 999 becoming 1000.
• Put a 1 at the front, the rest stay zero. The array grows by one box.

Why it is fast:

• Each digit is touched once.
• So it runs in O(n) time, where n is the number of digits.
• It usually changes the array in place, so the extra space is O(1).

This picture shows the dry run on [9, 9, 9]. Follow the carry as it moves left.

Steps to Solve

1. Start at the last index of the array.
2. If that digit is less than nine, add one to it and return the array. You are done.
3. If that digit is nine, set it to zero and move one step to the left.
4. Repeat until a digit is less than nine, or until you run off the left edge.
5. If you ran off the left edge, put a 1 at the front of the array and return it.

#include <stdio.h>

int main(void) {
    int digits[] = {1, 2, 3};
    int n = 3;

    int i = n - 1;
    while (i >= 0 && digits[i] == 9) {  // turn trailing nines into zeros
        digits[i] = 0;
        i--;
    }

    if (i < 0) {                        // every digit was a nine
        printf("[1");
        for (int k = 0; k < n; k++) printf(", %d", digits[k]);
        printf("]\n");
    } else {
        digits[i]++;                    // add one where there is room
        printf("[");
        for (int k = 0; k < n; k++) {
            printf("%d", digits[k]);
            if (k < n - 1) printf(", ");
        }
        printf("]\n");
    }
    return 0;
}

[1, 2, 4]

#include <iostream>
#include <vector>
using namespace std;

vector<int> plusOne(vector<int> digits) {
    int n = digits.size();
    for (int i = n - 1; i >= 0; i--) {
        if (digits[i] < 9) {       // room to add, no carry needed
            digits[i]++;
            return digits;
        }
        digits[i] = 0;             // nine becomes zero, carry moves left
    }
    digits.insert(digits.begin(), 1);  // all nines, grow by one box
    return digits;
}

int main() {
    vector<int> digits = {1, 2, 3};
    vector<int> result = plusOne(digits);
    cout << "[";
    for (int k = 0; k < (int)result.size(); k++) {
        cout << result[k];
        if (k < (int)result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[1, 2, 4]

import java.util.Arrays;

public class PlusOne {
    public static int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {      // room to add, no carry needed
                digits[i]++;
                return digits;
            }
            digits[i] = 0;            // nine becomes zero, carry moves left
        }
        int[] grown = new int[n + 1]; // all nines, grow by one box
        grown[0] = 1;
        return grown;
    }

    public static void main(String[] args) {
        int[] digits = { 1, 2, 3 };
        System.out.println(Arrays.toString(plusOne(digits)));
    }
}

[1, 2, 4]

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):  # walk from the last digit left
        if digits[i] < 9:                      # room to add, no carry needed
            digits[i] += 1
            return digits
        digits[i] = 0                          # nine becomes zero, carry left
    return [1] + digits                        # all nines, grow by one box


digits = [1, 2, 3]
print(plus_one(digits))

[1, 2, 4]

function plusOne(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {        // room to add, no carry needed
      digits[i]++;
      return digits;
    }
    digits[i] = 0;              // nine becomes zero, carry moves left
  }
  return [1, ...digits];        // all nines, grow by one box
}

const digits = [1, 2, 3];
console.log(plusOne(digits));

[ 1, 2, 4 ]

Let us walk through the Python version line by line. Code first, then the why.

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

for i in range(len(digits) - 1, -1, -1): walks the indexes from the last one down to zero. We go right to left because addition carries from the small digit to the big digit. So we start where the plus one lands.

if digits[i] < 9: checks if there is room. Any digit below nine can take a plus one without spilling over. So this is the place where the work ends.

digits[i] += 1 adds the one. There is no carry past this point. So the rest of the digits on the left stay the same.

return digits stops right away. Once we add without a carry, the job is done. We do not need to look at any more digits.

digits[i] = 0 runs only when the digit was a nine. Nine plus one is ten. The digit becomes zero and the carry moves to the next loop step on the left.

return [1] + digits runs only if the loop never returned early. That means every digit was a nine, so they are all zeros now. We add a fresh 1 at the front. That is how 999 becomes 1000.

⏱️ Time and Space Complexity

The naive convert idea is fine for tiny inputs but breaks on long numbers because of overflow. The backward pass touches each digit at most once, so it is O(n) time. It usually changes the array in place, so it is O(1) extra space. Only the all-nines case grows the array by one box.

🧩 Key Takeaways

• ✅ The number is stored as separate digits, with the most important digit first.
• ✅ Start at the rightmost digit and walk left, just like adding on paper.
• ✅ A digit below nine takes the plus one and you stop right away.
• ✅ A nine becomes a zero and carries one to the left.
• ✅ If every digit is a nine, put a 1 at the front so the array grows by one box.

🚀 What’s Next?

• Can Place Flowers
• Next Permutation