题目描述
给你正整数 low
,high
和 k
。
如果一个数满足以下两个条件,那么它是 美丽的:
- 偶数数位的数目与奇数数位的数目相同。
- 这个整数可以被
k
整除。
请你返回范围 [low, high]
中美丽整数的数目。
样例
输入: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 个美丽整数。
输入:low = 1, high = 10, k = 1
输出:1
解释:给定范围中有 1 个美丽数字:[10]
- 10 是美丽整数,因为它有 1 个奇数数位和 1 个偶数数位,而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。
输入:low = 5, high = 5, k = 2
输出:0
解释:给定范围中有 0 个美丽数字。
- 5 不是美丽整数,因为它的奇数数位和偶数数位的数目不相等。
限制
0 < low <= high <= 10^9
0 < k <= 20
算法
(数位统计) $O(|\Sigma| k \log^2 n)$
- 首先预处理一些状态:设 $f(len, i, j)$ 表示长度为 $len$ 的 包含前导零 数字,有 $i$ 个奇数数位,且模 $k$ 的余数为 $j$ 时的总数;对应地,$g(len, i, j)$ 表示 不包含前导零 的数字个数。
- 先求 $f$:
- 初始时,$f(0, 0, 0) = 1$ 对应 空数字 的情况;$f(1, num \% 2, num \% k) = 1$,对应 包括零 在内所有一位数的情况,其余为 $0$ 待定。
- 转移时,对于 $f(len, i, j)$,枚举新的最低位的数字 $num$(包括零),如果 $num$ 为偶数,则 $f(len + 1, i, (10 \cdot j + num) \% k) = f(len + 1, i, (10 \cdot j + num) \% k) + f(len, i, j)$。
- 如果 $num$ 为奇数,则 $f(len + 1, i + 1, (10 \cdot j + num) \% k) = f(len + 1, i + 1, (10 \cdot j + num) \% k) + f(len, i, j)$。
- 对于 $g$,初始化和 $f$ 有所不同,转移过程都相同。由于不能含前导零,所以 $g(1, num \% 2, num \% k) = 1$,对应 不包括零 在内所有一位数的情况,其余为 $0$ 待定。也就是首位不能为 $0$。
- 接着进入数位统计阶段,将 $[low, hight]$ 分解为 $solve[high] - [low - 1]$,$solve[x]$ 表示求解小于等于 $x$ 的正整数的答案。
- 将 $x$ 的所有数位放到数组中,从最高位开始到最低位统计,假设 $x$ 的数位长度为 $m$。
- 首先统计数位长度严格小于 $m$ 的方案数,这里就用到了 不包含前导零 的预处理状态,$len$ 从小于 $m$ 的最近一个偶数开始,直到 $2$,累加 $g(len, len / 2, 0)$ 到答案中。
- 接着统计数位长度等于 $m$ 的方案数,如果 $m$ 为奇数,则直接结束。如果为偶数,则从高位开始往低位遍历,过程中累加答案。
- 具体地,遍历过程中记录已遍历数字中奇数的个数 $odd$,已遍历数字组成的数字 $tot$。遍历时,枚举当前位可以填充的数字 $num$(对于最高位,则 $[1, t - 1]$,对于其他位,为 $[0, t - 1]$,其中 $t$ 为当前数位的数字。对于枚举的 $num$,如果为奇数,则可以累加答案 $f(len - 1, m / 2 - odd, (k - tot + num \cdot 10^{len - 1}) \% k)$,也就是确定了当前位后,后续低位 含前导零 任意组合最终拼凑成合法情况的方案数。对于 $num$ 为偶数同理。
- 最终别忘了对于给定的 $x$ 判定是否合法。
时间复杂度
- 预处理的时间复杂度为 $O(|\Sigma| k \log^2 n)$,其中 $|Sigma|$ 为数字集合的大小,这里等于 $10$。
- 数位统计的时间复杂度为 $O(|\Sigma| \log n)$。
- 故总时间复杂度为 $O(|\Sigma| k \log^2 n)$。
空间复杂度
- 需要 $O(k \log^2 n)$ 的额外空间存储预处理状态。
C++ 代码
const int N = 10, K = 20;
class Solution {
private:
int f[N][N][K], g[N][N][K];
void init(int k) {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
f[0][0][0] = f[1][0][0] = 1;
for (int num = 1; num < 10; num++) {
++f[1][num % 2][num % k];
++g[1][num % 2][num % k];
}
for (int len = 1; len < N - 1; len++)
for (int i = 0; i <= len; i++)
for (int j = 0; j < k; j++)
for (int num = 0; num < 10; num++) {
if (num % 2 == 0) {
f[len + 1][i][(j * 10 + num) % k] += f[len][i][j];
g[len + 1][i][(j * 10 + num) % k] += g[len][i][j];
} else {
f[len + 1][i + 1][(j * 10 + num) % k] += f[len][i][j];
g[len + 1][i + 1][(j * 10 + num) % k] += g[len][i][j];
}
}
}
int solve(int x, int k) {
if (x == 0)
return 0;
vector<int> nums;
int power = 1;
while (x >= 10) {
nums.push_back(x % 10);
x /= 10;
power *= 10;
}
nums.push_back(x);
int ans = 0;
const int m = nums.size();
for (int len = m % 2 ? m - 1 : m - 2; len >= 2; len -= 2)
ans += g[len][len / 2][0];
if (m % 2 != 0)
return ans;
int tot = 0, odd = 0;
for (int len = m; len >= 1; len--) {
int t = nums[len - 1];
for (int num = (len == m) ? 1 : 0; num < t; num++) {
int tk = (k - (tot + num * power) % k) % k;
if (num % 2 == 0 && m / 2 >= odd)
ans += f[len - 1][m / 2 - odd][tk];
else if (num % 2 == 1 && m / 2 >= odd + 1)
ans += f[len - 1][m / 2 - odd - 1][tk];
}
tot += t * power;
odd += t % 2;
power /= 10;
}
if (m % 2 == 0 && odd == m / 2 && tot % k == 0)
++ans;
return ans;
}
public:
int numberOfBeautifulIntegers(int low, int high, int k) {
init(k);
return solve(high, k) - solve(low - 1, k);
}
};