What is a beautiful integer in this problem?

A beautiful integer has equal numbers of even and odd digits and is divisible by k.

Which dynamic programming pattern is used here?

State transition dynamic programming tracks digit positions, parity counts, and modulo to count valid numbers.

Can this approach handle large ranges efficiently?

Yes, memoization ensures performance even when high is up to 10^9 by avoiding redundant calculations.

How do I initialize the DP table?

Start with position 0, tight constraint true, evenCount and oddCount 0, and mod 0, then recursively fill states.

What should I watch out for in implementation?

Avoid miscounting parity digits, ensure modulo updates correctly, and respect tight bounds to prevent overcounting.

#2827

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

范围中美丽整数的数目

给你正整数 low ， high 和 k 。如果一个数满足以下两个条件，那么它是美丽的：偶数数位的数目与奇数数位的数目相同。这个整数可以被 k 整除。请你返回范围 [low, high] 中美丽整数的数目。示例 1：输入： low = 10, high = 20, k = 3 输出：…

数学动态规划

题目描述

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。

请你返回范围 [low, high] 中美丽整数的数目。

示例 1：

输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽数字：[12,18]
- 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
- 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：
- 16 不是美丽整数，因为它不能被 k = 3 整除。
- 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。

示例 2：

输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽数字：[10]
- 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。

示例 3：

输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽数字。
- 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

提示：

0 < low <= high <= 10⁹
0 < k <= 20

lightbulb

解题思路

方法一：数位 DP

我们注意到，题目求的是区间 $[low, high]$ 内的美丽整数的个数，对于这种区间 $[l,..r]$ 的问题，我们通常可以考虑转化为求 $[1, r]$ 和 $[1, l-1]$ 的答案，然后相减即可。另外，题目中只涉及到不同数位之间的关系，而不涉及具体的数值，因此我们可以考虑使用数位 DP 来解决。

我们设计一个函数 $dfs(pos, mod, diff, lead, limit)$ ，表示当前处理到第 $pos$ 位，当前数字模 $k$ 的结果为 $mod$ ，当前数字的奇偶数位差为 $diff$ ，当前数字是否有前导零为 $lead$ ，当前数字是否达到上界为 $limit$ 时的方案数。

函数 $dfs(pos, mod, diff, lead, limit)$ 的执行逻辑如下：

如果 $pos$ 超出了 $num$ 的长度，说明我们已经处理完了所有数位，如果此时 $mod=0$ ，并且 $diff=0$ ，说明当前数字满足题目要求，我们返回 $1$ ，否则返回 $0$ 。

否则，我们计算得到当前数位的上界 $up$ ，然后在 $[0,..up]$ 范围内枚举当前数位的数字 $i$ ：

如果 $i=0$ 且 $lead$ 为真，说明当前数字只包含前导零，我们递归计算 $dfs(pos + 1, mod, diff, 1, limit\ and\ i=up)$ 的值并累加到答案中；
否则，我们根据 $i$ 的奇偶性更新 $diff$ 的值，然后递归计算 $dfs(pos + 1, (mod \times 10 + i) \bmod k, diff, 0, limit\ and\ i=up)$ 的值并累加到答案中。

最终我们返回答案。

在主函数中，我们分别计算 $[1, high]$ 和 $[1, low-1]$ 的答案 $a$ 和 $b$ ，最终答案为 $a-b$ 。

时间复杂度 $O((\log M)^2 \times k \times |\Sigma|)$ ，空间复杂度 $O((\log M)^2 \times k \times)$ ，其中 $M$ 表示 $high$ 数字的大小，而 $|\Sigma|$ 表示数字集合。

相似题目：

2719. 统计整数数目

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        @cache
        def dfs(pos: int, mod: int, diff: int, lead: int, limit: int) -> int:
            if pos >= len(s):
                return mod == 0 and diff == 10
            up = int(s[pos]) if limit else 9
            ans = 0
            for i in range(up + 1):
                if i == 0 and lead:
                    ans += dfs(pos + 1, mod, diff, 1, limit and i == up)
                else:
                    nxt = diff + (1 if i % 2 == 1 else -1)
                    ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, 0, limit and i == up)
            return ans

        s = str(high)
        a = dfs(0, 0, 10, 1, 1)
        dfs.cache_clear()
        s = str(low - 1)
        b = dfs(0, 0, 10, 1, 1)
        return a - b

speed

复杂度分析

指标	值
时间	and space complexity depend on the number of digits and k. The DP table has dimensions proportional to number of digits, parity difference, and modulo k, resulting in manageable memory and polynomial runtime relative to digit length and k.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate correctly identifies digit DP as a viable approach.
question_mark
Shows understanding of state transitions for even/odd counts and modulo k.
question_mark
Uses memoization effectively to handle large ranges up to 10^9.

warning

常见陷阱

外企场景

error
Confusing digit parity counting or forgetting to track both even and odd digits.
error
Neglecting the modulo k constraint when updating DP states.
error
Failing to handle tight constraint correctly, causing overcounting beyond high.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count numbers with more even digits than odd digits divisible by k.
arrow_right_alt
Find numbers with alternating odd and even digits within a range divisible by k.
arrow_right_alt
Compute numbers with exact digit sum divisible by k and balanced parity.

help

常见问题

外企场景

继续练习

#2851 字符串转换 #2867 统计树中的合法路径数目 #2750 将数组划分成若干好子数组的方式