Abstract / Summary

Add one to a number represented as a list of digits and return the new list of digits.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (7+ million submissions).

Typical patterns to solve this problem:

• Array
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “plus one” problem: given a non-empty array of decimal digits representing a non-negative integer, it returns a new array that represents the integer plus one. The algorithm works directly on the input vector, mutating it in place and only allocating additional memory when a carry propagates beyond the most significant digit.

Key Steps

The first logical block prepares a flag that indicates whether a carry remains after processing each digit. The loop iterates from the least significant digit toward the most significant one, incrementing the current digit and handling overflow.

bool more = true;
for (int i = digits.size() - 1; i >= 0; i--)
{
    more = false;
    digits[i]++;
    if (digits[i] < 10)
        break;
    more = true;
    digits[i] = 0;
}

Inside the loop the digit is incremented. If the result stays below ten, the carry is resolved and the loop exits early. When the digit reaches ten, it is reset to zero and the more flag stays true, indicating that the carry must continue to the next higher position.

After the loop finishes, a final check determines whether the most significant position also overflowed. If more is still true, a new digit 1 is inserted at the front of the vector, extending its length by one.

if (more)
    digits.insert(digits.begin(), 1);

The function then returns the possibly modified vector.

return digits;

Edge Cases

The algorithm gracefully handles the scenario where every digit in the input is 9. In such a case each iteration resets the current digit to 0 and propagates the carry leftward. When the loop reaches the most significant digit and still has a carry (more remains true), the insertion of 1 at the beginning produces the correct result, e.g., [9,9,9] becomes [1,0,0,0].

Another edge case is a single-digit input that is not 9. The loop increments the digit, the condition digits[i] < 10 becomes true, and the loop breaks immediately without any further work. The more flag is set to false, so no insertion occurs, yielding the correct single-digit result.

The code also correctly processes inputs where the least significant digit is not 9. The early break after the first increment avoids unnecessary iterations, leaving the higher-order digits untouched.

Performance Optimizations

The implementation minimizes work by breaking out of the loop as soon as the carry is resolved. This early exit prevents needless traversal of the remaining higher-order digits when they are unaffected by the addition.

Memory allocation occurs only when a new most-significant digit is required. The use of vector::insert at the beginning is invoked solely in the overflow case, avoiding extra copies for the common path where the length stays unchanged.

By mutating the original vector in place, the algorithm avoids constructing a separate result container, reducing both allocation overhead and copying cost. The overall flow leverages simple integer operations and a single pass over the digits, ensuring efficient execution even for large input sizes.

Imagine you have a row of number blocks sitting on a table, and each block shows a single digit. This collection of blocks makes up one big number. To add one to this big number, the plan starts by looking at the very last block on the right side.

The process picks up that last block and adds one to the number showing on its face. If that block still shows a single digit from zero to nine, the job is finished because the number is ready. However, if the block turns into a ten, it cannot hold two digits at once. So, the block changes to a zero, and the process moves to the neighbor on the left to add one to that block instead.

This pattern continues from right to left just like a wave. If the blocks keep turning into tens, the rule keeps resetting them to zero and moving left. If the wave travels all the way to the front and the very first block also turns into a ten, a new block showing the number one is added at the very beginning of the line. Now the big number is increased by one exactly as it should be.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java					TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java	Rust	JS	Go		TS
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	aylei						Rust
	begeekmyfriend				C
	BigEggStudy			C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai					Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem									Ruby
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong					Java
	ruoru						Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28					Java
	vli02				C
	withaarzoo	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
withaarzoo	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality