What is the main trick in Numbers With Repeated Digits?

The main trick is to count numbers with all distinct digits up to n, then subtract that count from n. Counting the complement is much simpler than enumerating every repeated-digit pattern directly.

Why is state transition dynamic programming a good fit here?

Each digit choice depends on previous choices, the used digits, and whether the current prefix is still tied to n. That dependency structure is exactly what digit DP handles well.

Do I need a separate formula for numbers with fewer digits than n?

Not necessarily. A started flag with leading-zero transitions lets one digit DP cover both shorter numbers and full-length numbers without messy special cases.

Why does n = 20 return 1?

From 1 to 20, every number has distinct digits except 11. So the repeated-digit count is exactly 1.

What is the most common bug in this problem title?

The most common bug in Numbers With Repeated Digits is mishandling leading zeros so that digit 0 is treated as already used before the number starts. That breaks counts for shorter valid numbers and usually produces wrong subtraction at the end.

#1012

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

至少有 1 位重复的数字

给定正整数 n ，返回在 [1, n] 范围内具有至少 1 位重复数字的正整数的个数。示例 1：输入： n = 20 输出： 1 解释：具有至少 1 位重复数字的正数（示例 2：输入： n = 100 输出： 10 解释：具有至少 1 位重复数字的正数（示例 3：输入： n = …

数学动态规划

题目描述

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

示例 1：

输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。

示例 2：

输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。

示例 3：

输入：n = 1000
输出：262

提示：

1 <= n <= 10⁹

lightbulb

解题思路

方法一：状态压缩 + 数位 DP

题目要求统计 $[1,..n]$ 中至少有一位重复的数字的个数，我们可以换一种思路，用一个函数 $f(n)$ 统计 $[1,..n]$ 中没有重复数字的个数，那么答案就是 $n - f(n)$ 。

另外，我们可以用一个二进制数来记录数字中出现过的数字，比如数字中出现了 $1$ , $2$ , $4$ ，那么对应的二进制数就是 $\underline{1}0\underline{1}\underline{1}0$ 。

接下来，我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。

基本步骤如下：

我们将数字 $n$ 转为字符串 $s$ ，接下来，我们设计一个函数 $\textit{dfs}(i, \textit{mask}, \textit{lead}, \textit{limit})$ ，其中：

数字 $i$ 表示当前处理的数字下标，从 $0$ 开始。
数字 $\textit{mask}$ 表示当前数字中出现过的数字，用二进制数表示。其中 $\textit{mask}$ 的二进制的第 $j$ 位为 $1$ 表示数字 $j$ 出现过，为 $0$ 表示数字 $j$ 没有出现过。
布尔值 $\textit{lead}$ 表示是否只包含前导零。
布尔值 $\textit{limit}$ 表示当前位置是否受到上界的限制。

函数的执行过程如下：

如果 $i$ 大于等于 $m$ ，说明我们已经处理完了所有的位数，此时如果 $\textit{lead}$ 为真，说明当前的数字是前导零，我们应当返回 $0$ ；否则，我们应当返回 $1$ 。

否则，我们计算当前位置的上界 $\textit{up}$ ，如果 $\textit{limit}$ 为真，则 $up$ 为 $s[i]$ 对应的数字，否则 $up$ 为 $9$ 。

然后，我们在 $[0, \textit{up}]$ 的范围内枚举当前位置的数字 $j$ ，如果 $j$ 为 $0$ 且 $\textit{lead}$ 为真，我们递归计算 $\textit{dfs}(i + 1, \textit{mask}, \text{true}, \textit{limit} \wedge j = \textit{up})$ ；否则，如果 $\textit{mask}$ 的第 $j$ 位为 $0$ ，我们递归计算 $\textit{dfs}(i + 1, \textit{mask} \,|\, 2^j, \text{false}, \textit{limit} \wedge j = \textit{up})$ 。累加所有的结果即为答案。

答案为 $n - \textit{dfs}(0, 0, \text{true}, \text{true})$ 。

时间复杂度 $O(\log n \times 2^D \times D)$ ，空间复杂度 $O(\log n \times 2^D)$ 。其中 $D = 10$ 。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        @cache
        def dfs(i: int, mask: int, lead: bool, limit: bool) -> int:
            if i >= len(s):
                return lead ^ 1
            up = int(s[i]) if limit else 9
            ans = 0
            for j in range(up + 1):
                if lead and j == 0:
                    ans += dfs(i + 1, mask, True, False)
                elif mask >> j & 1 ^ 1:
                    ans += dfs(i + 1, mask | 1 << j, False, limit and j == up)
            return ans

        s = str(n)
        return n - dfs(0, 0, True, True)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They hint at counting numbers with no duplicate digits first instead of constructing repeated-digit numbers directly.
question_mark
They ask how many valid numbers exist with exactly K digits, pointing you toward permutations and digit-state transitions.
question_mark
They focus on prefix decisions against n, which is a strong signal for digit DP with a tight bound.

warning

常见陷阱

外企场景

error
Forgetting that leading zeros should not mark digit 0 as used, which corrupts counts for shorter numbers.
error
Subtracting the wrong baseline by including 0 as a positive integer, which shifts the final answer by one.
error
Trying to count repeated-digit cases directly and double-counting numbers that repeat more than one digit or repeat in multiple positions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the count of numbers in [1, n] with all distinct digits instead of repeated digits.
arrow_right_alt
Count numbers in an arbitrary range [a, b] by computing the result up to b and subtracting the result up to a - 1.
arrow_right_alt
Change the rule from any repeated digit to exactly one repeated digit, which requires a richer DP state than a simple used-digit mask.

help

常见问题

外企场景

继续练习

#1025 除数博弈 #996 平方数组的数目 #964 表示数字的最少运算符