Plus One — Carry Propagation Array Trick [Easy Interview Problem]

Problem Statement

You are given a large integer represented as an array of digits, where each digits[i] is the i-th digit. The digits are stored in most-significant-first order. Increment the integer by one and return the resulting array.

Examples:

Input:  [1, 2, 3]  → Output: [1, 2, 4]  (123 + 1 = 124)
Input:  [9]        → Output: [1, 0]      (9 + 1 = 10)
Input:  [9, 9, 9]  → Output: [1, 0, 0, 0] (999 + 1 = 1000)

Intuition
Solutions in All 5 Languages
C
C++
Java
JavaScript
Python
Complexity: O(n) time, O(1) space (O(n) for the all-9s edge case)

Intuition

Walk from the last digit to the first (right to left). Add 1. If the digit becomes 10, set it to 0 and carry 1 to the next position. If we exit the loop with carry still 1, prepend a 1.

for i from n-1 downto 0:
    digits[i] += 1
    if digits[i] < 10: return digits  ← no more carry
    digits[i] = 0                     ← carry continues

return [1] + digits  ← all 9s case: 999...9 → 1000...0

Solutions in All 5 Languages

C

#include <stdlib.h>

int* plusOne(int* digits, int digitsSize, int* returnSize) {
    // Walk from right, handle carry
    for (int i = digitsSize - 1; i >= 0; i--) {
        digits[i]++;
        if (digits[i] < 10) {
            *returnSize = digitsSize;
            return digits;
        }
        digits[i] = 0;
    }
    // All digits were 9 → need new array with leading 1
    int* result = (int*)calloc(digitsSize + 1, sizeof(int));
    result[0] = 1;
    *returnSize = digitsSize + 1;
    return result;
}

C++

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            if (++digits[i] < 10) return digits;
            digits[i] = 0;
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

Java

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (++digits[i] < 10) return digits;
            digits[i] = 0;
        }
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }
}

JavaScript

function plusOne(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (++digits[i] < 10) return digits;
        digits[i] = 0;
    }
    return [1, ...digits];
}

Python

from typing import List

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):
            digits[i] += 1
            if digits[i] < 10:
                return digits
            digits[i] = 0
        return [1] + digits

Complexity: O(n) time, O(1) space (O(n) for the all-9s edge case)

Next: Problem 7 — Merge Sorted Array →