Abstract / Summary

Count how many numbers with all different digits exist up to a given limit.

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 56% (300k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Dynamic Programming
• 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 computes the total count of non-negative integers whose decimal representation contains no repeated digits, for all lengths from 0 up to a given n. The algorithm builds the answer incrementally: it starts with the base case for length 0 and then adds the contribution of each length 1…n using a closed-form combinatorial helper.

Key Steps

Definition of the combinatorial helper

def A073531(n):
    return 9 * factorial(9) // factorial(10 - n)

This inner function implements the formula for the number of n-digit numbers with all distinct digits, assuming the most significant digit cannot be zero. The expression 9 * factorial(9) // factorial(10 - n) directly evaluates the product

9 × 9 × 8 × 7 × … × (10-n)

by leveraging the factorial function, thereby avoiding explicit loops for the multiplication chain.

Initialization of the accumulator

result = 1

The variable result is seeded with 1, which accounts for the single valid number of length 0 - the integer 0 itself. This establishes the correct base for the cumulative sum.

Iterative accumulation over lengths

for i in range(1, n+1):
    result += A073531(i)

The loop iterates from 1 through n, invoking the combinatorial helper for each length i and adding its return value to result. Because the helper already returns the exact count for the current length, the loop simply aggregates the totals for all lengths up to n.

Final return

return result

After the loop finishes, result holds the sum of counts for lengths 0…n, which is the required answer.

Edge Cases Handled

When n equals 0, the for loop’s range becomes empty, so the body is never executed. The function therefore returns the initial value of result, which is 1 - correctly representing the sole number 0 that satisfies the uniqueness condition for length 0.

The helper A073531 is defined for n values from 1 up to 9. For n = 1 the expression evaluates to 9 * factorial(9) // factorial(9), yielding 9, which together with the base case gives the expected total of 10 (the digits 0-9). For n = 9 the denominator becomes factorial(1), and the formula computes the full set of 9-digit numbers with distinct digits. The implementation therefore gracefully covers the full range of meaningful inputs where distinct-digit numbers exist.

Performance Optimizations

The use of the factorial-based closed form in A073531 eliminates the need for nested loops or repeated multiplication for each digit position. By calling factorial from the standard library, the code benefits from a highly optimized C implementation, which computes the factorial values quickly and with minimal overhead.

The outer loop runs exactly n times, and each iteration performs only a constant-time arithmetic operation (a function call and an addition). This linear progression is optimal for the problem’s domain, where n never exceeds 9 in practice, so the total work remains trivial even for the maximum input.

Because all intermediate results are integers and Python’s arbitrary-precision arithmetic handles them without overflow, the algorithm avoids any extra checks or conversions, keeping the execution path tight and efficient.

Imagine having a giant box of number blocks, and the goal is to count how many special numbers can be made using those blocks. Every block has a number from zero to nine, but there is a rule that every block in a number must be different.

The code starts by knowing that the number zero is a special case that counts as one. Then, it goes on a little journey to check numbers with one digit, then two, then three, and so on, depending on how big the number chosen is.

Inside the loop, the code uses a helper tool that figures out how many ways different digits can be placed in a row without ever repeating the same digit. For each size, the code does a quick calculation of all those possible unique combinations. It keeps adding these counts to a growing pile until it finishes checking all the sizes asked for. By the end, the growing pile holds the total count of every single number that does not have any repeating digits.

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			Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis			JS
	halfrost							Go
	haoel	C++
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	yuanliu666						Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
yuanliu666	Kotlin
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