题目描述
给你一个整数 k
和一个整数 x
。
令 s
为整数 num
的下标从 1 开始的二进制表示。我们说一个整数 num
的 价值 是满足 i % x == 0
且 s[i]
是 设置位 的 i
的数目。
请你返回 最大 整数 num
,满足从 1
到 num
的所有整数的 价值 和小于等于 k
。
注意:
- 一个整数二进制表示下 设置位 是值为
1
的数位。 - 一个整数的二进制表示下标从右到左编号,比方说如果
s == 11100
,那么s[4] == 1
且s[2] == 0
。
样例
输入:k = 9, x = 1
输出:6
解释:数字 1,2,3,4,5 和 6 二进制表示分别为 "1","10","11","100","101" 和 "110"。
由于 x 等于 1 ,每个数字的价值分别为所有设置位的数目。
这些数字的所有设置位数目总数是 9,所以前 6 个数字的价值和为 9。
所以答案为 6。
输入:k = 7, x = 2
输出:9
解释:由于 x 等于 2,我们检查每个数字的偶数位。
2 和 3 在二进制表示下的第二个数位为设置位,所以它们的价值和为 2。
6 和 7 在二进制表示下的第二个数位为设置位,所以它们的价值和为 2。
8 和 9 在二进制表示下的第四个数位为设置位但第二个数位不是设置位,所以它们的价值和为 2。
数字 1,4 和 5 在二进制下偶数位都不是设置位,所以它们的价值和为 0。
10 在二进制表示下的第二个数位和第四个数位都是设置位,所以它的价值为 2。
前 9 个数字的价值和为 6。
前 10 个数字的价值和为 8,超过了 k = 7,所以答案为 9。
限制
1 <= k <= 10^15
1 <= x <= 8
算法
(二分答案,数位统计) $O((x + \log k) ^ 2)$
- 我们可以二分最后的
num
,判定1
到num
中符合要求的设置位总数量。 - 通过递推预处理长度为 $i$ 的数位中,符合要求的设置位的总数量 $f(i)$。递推的思路是,最高位填充 $0$ 或者填充 $1$,$f(i) = 2f(i - 1)$,当第 $i$ 位模 $x$ 等于 0 时,高位填充的 1 可以再共享 $2^{i-1}$ 个设置位。
- 对于给定的二分值 $mid$,从高位到低位依次遍历,统计符合要求的设置位。具体地,对于第 $i$ 个二进制位,如果这一位的值为 $0$,则直接忽略;否则,假设当前位填充 $0$,后面的低位贡献 $f(i - 1)$ 个有效位。前面已经填充好的数位中,有 $num$ 个符合要求的设置位,此时可以贡献 $num \cdot 2^{i-1}$ 个设置位。
时间复杂度
- 二分的下限为 $1$,上限为 $k\cdot 2^x$。
- 每次二分,都需要 $O(\log k\cdot 2^x) = $O(x + \log k)$ 的时间。
- 故总时间复杂度为 $O((x + \log k)^2)$。
空间复杂度
- 需要 $O(x + \log k)$ 的额外空间存储预处理的数组。
C++ 代码
#define LL long long
const int N = 57;
class Solution {
private:
LL f[N];
LL calc(LL n, int x) {
LL res = 0;
int num = 0;
for (int i = N - 1; i >= 0; i--) {
if (!((n >> i) & 1))
continue;
res += f[i] + (LL)(num) * (1ll << i);
if ((i + 1) % x == 0)
++num;
}
return res + num;
}
public:
LL findMaximumNumber(LL k, int x) {
f[0] = 0;
for (int i = 1; i < N; i++) {
f[i] = 2 * f[i - 1];
if (i % x == 0)
f[i] += 1ll << (i - 1);
}
LL l = 1, r = (1 << x) * k;
while (l < r) {
LL mid = (l + r) >> 1;
if (calc(mid + 1, x) <= k) l = mid + 1;
else r = mid;
}
return l;
}
};
你把它发在这里干嘛?