class Solution {
public:
long long findMaximumNumber(long long k, int x) {
}
};
3007. 价值和小于等于 K 的最大数字
给你一个整数 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 。
示例 1：
输入：k = 9, x = 1 输出：6 解释：数字 1 ，2 ，3 ，4 ，5 和 6 二进制表示分别为 "1" ，"10" ，"11" ，"100" ，"101" 和 "110" 。 由于 x 等于 1 ，每个数字的价值分别为所有设置位的数目。 这些数字的所有设置位数目总数是 9 ，所以前 6 个数字的价值和为 9 。 所以答案为 6 。
示例 2：
输入：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 <= 10151 <= x <= 8原站题解
javascript 解法, 执行用时: 98 ms, 内存消耗: 57 MB, 提交时间: 2024-08-21 09:31:06
/**
* @param {number} k
* @param {number} x
* @return {number}
*/
var findMaximumNumber = function(k, x) {
let l = 1n, r = (BigInt(k) + 1n) << BigInt(x);
while (l < r) {
let m = (l + r + 1n) / 2n;
if (accumulatedPrice(x, m) > k) {
r = m - 1n;
} else {
l = m;
}
}
return Number(l);
};
function accumulatedBitPrice(x, num) {
const period = 1n << BigInt(x);
let res = period / 2n * (num / period);
if (num % period >= period / 2n) {
res += num % period - (period / 2n - 1n);
}
return res;
}
function accumulatedPrice(x, num) {
let res = 0n;
const length = 64 - Math.clz32(Number(num >> 32n));
for (let i = x; i <= length; i += x) {
res += accumulatedBitPrice(i, num);
}
return res;
}
rust 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2024-08-21 09:29:00
impl Solution {
pub fn find_maximum_number(k: i64, x: i32) -> i64 {
let (mut l, mut r) = (1i64, (k + 1) << x);
while l < r {
let m = (l + r + 1) / 2;
if Self::accumulated_price(x, m) > k {
r = m - 1;
} else {
l = m;
}
}
return l;
}
fn accumulated_bit_price(x: i32, num: i64) -> i64 {
let period = 1i64 << x;
let mut res = period / 2 * (num / period);
if num % period >= period / 2 {
res += num % period - (period / 2 - 1);
}
return res;
}
fn accumulated_price(x: i32, num: i64) -> i64 {
let mut res = 0i64;
let length = 64 - num.leading_zeros();
for i in (x..=length as i32).step_by(x as usize) {
res += Self::accumulated_bit_price(i, num);
}
return res;
}
}
golang 解法, 执行用时: 3 ms, 内存消耗: 2.1 MB, 提交时间: 2024-01-21 20:39:26
func findMaximumNumber(K int64, x int) int64 {
k := int(K)
num, pre1 := 0, 0
for i := bits.Len(uint((k+1)<<x)) - 1; i >= 0; i-- {
cnt := pre1<<i + i/x<<i>>1
if cnt > k {
continue
}
k -= cnt
num |= 1 << i
if (i+1)%x == 0 {
pre1++
}
}
return int64(num - 1)
}
func findMaximumNumber2(k int64, x int) int64 {
ans := sort.Search(int(k+1)<<x, func(num int) bool {
num++
res := 0
i := x - 1
for n := num >> i; n > 0; n >>= x {
res += n / 2 << i
if n%2 > 0 {
mask := 1<<i - 1
res += num&mask + 1
}
i += x
}
return res > int(k)
})
return int64(ans)
}
func findMaximumNumber3(k int64, x int) int64 {
ans := sort.Search(int(k+1)<<x, func(num int) bool {
num++
n := bits.Len(uint(num))
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int, bool) int
dfs = func(i, cnt1 int, limitHigh bool) (res int) {
if i < 0 {
return cnt1
}
if !limitHigh {
p := &memo[i][cnt1]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
up := 1
if limitHigh {
up = num >> i & 1
}
for d := 0; d <= up; d++ {
c := cnt1
if d == 1 && (i+1)%x == 0 {
c++
}
res += dfs(i-1, c, limitHigh && d == up)
}
return
}
return dfs(n-1, 0, true) > int(k)
})
return int64(ans)
}
cpp 解法, 执行用时: 498 ms, 内存消耗: 353.3 MB, 提交时间: 2024-01-21 20:38:43
class Solution {
public:
long long findMaximumNumber(long long k, int x) {
auto check = [&](long long num) {
int m = 64 - __builtin_clzll(num);
vector<vector<long long>> memo(m, vector<long long>(m + 1, -1));
function<long long(int, int, bool)> dfs = [&](int i, int cnt1, bool is_limit) -> long long {
if (i < 0) return cnt1;
if (!is_limit && memo[i][cnt1] >= 0) return memo[i][cnt1];
int up = is_limit ? num >> i & 1 : 1;
long long res = 0;
for (int d = 0; d <= up; d++) // 枚举要填入的数字 d
res += dfs(i - 1, cnt1 + (d == 1 && (i + 1) % x == 0), is_limit && d == up);
if (!is_limit) memo[i][cnt1] = res;
return res;
};
return dfs(m - 1, 0, true) <= k;
};
// 开区间二分，原理见 https://www.bilibili.com/video/BV1AP41137w7/
long long left = 0, right = (k + 1) << x;
while (left + 1 < right) {
long long mid = left + (right - left) / 2;
(check(mid) ? left : right) = mid;
}
return left;
}
long long findMaximumNumber2(long long k, int x) {
auto check = [&](long long num) {
long long res = 0;
int i = x - 1;
for (long long n = num >> i; n; n >>= x, i += x) {
res += (n / 2) << i;
if (n % 2) {
long long mask = (1LL << i) - 1;
res += (num & mask) + 1;
}
}
return res <= k;
};
// 开区间二分，原理见 https://www.bilibili.com/video/BV1AP41137w7/
long long left = 0, right = (k + 1) << x;
while (left + 1 < right) {
long long mid = left + (right - left) / 2;
(check(mid) ? left : right) = mid;
}
return left;
}
long long findMaximumNumber3(long long k, int x) {
long long num = 0, pre1 = 0;
for (long long i = 63 - __builtin_clzll((k + 1) << x); i >= 0; i--) {
long long cnt = (pre1 << i) + (i / x << i >> 1);
if (cnt <= k) {
k -= cnt;
num |= 1LL << i;
pre1 += (i + 1) % x == 0;
}
}
return num - 1;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39.9 MB, 提交时间: 2024-01-21 20:37:53
class Solution {
public long findMaximumNumber(long k, int x) {
long num = 0, pre1 = 0;
for (long i = 63 - Long.numberOfLeadingZeros((k + 1) << x); i >= 0; i--) {
long cnt = (pre1 << i) + (i / x << i >> 1);
if (cnt > k) {
continue;
}
k -= cnt;
num |= 1L << i;
if ((i + 1) % x == 0) {
pre1++;
}
}
return num - 1;
}
}
class Solution2 {
public long findMaximumNumber(long k, int x) {
// 开区间二分，原理见 https://www.bilibili.com/video/BV1AP41137w7/
long left = 0;
long right = (k + 1) << x;
while (left + 1 < right) {
long mid = (left + right) >>> 1;
if (countDigitOne(mid, x) <= k) {
left = mid;
} else {
right = mid;
}
}
return left;
}
private long countDigitOne(long num, int x) {
long res = 0;
int i = x - 1;
for (long n = num >> i; n > 0; n >>= x, i += x) {
res += (n / 2) << i;
if (n % 2 > 0) {
long mask = (1L << i) - 1;
res += (num & mask) + 1;
}
}
return res;
}
}
class Solution3 {
public long findMaximumNumber(long k, int x) {
this.x = x;
// 开区间二分，原理见 https://www.bilibili.com/video/BV1AP41137w7/
long left = 0;
long right = (k + 1) << x;
while (left + 1 < right) {
long mid = (left + right) >>> 1;
if (countDigitOne(mid) <= k) {
left = mid;
} else {
right = mid;
}
}
return left;
}
private int x;
private long num;
private long memo[][];
private long countDigitOne(long num) {
this.num = num;
int m = 64 - Long.numberOfLeadingZeros(num);
memo = new long[m][m + 1];
for (long[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(m - 1, 0, true);
}
private long dfs(int i, int cnt1, boolean isLimit) {
if (i < 0) return cnt1;
if (!isLimit && memo[i][cnt1] != -1) return memo[i][cnt1];
int up = isLimit ? (int) (num >> i & 1) : 1;
long res = 0;
for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d
res += dfs(i - 1, cnt1 + (d == 1 && (i + 1) % x == 0 ? 1 : 0), isLimit && d == up);
}
if (!isLimit) memo[i][cnt1] = res;
return res;
}
}
python3 解法, 执行用时: 49 ms, 内存消耗: 16.4 MB, 提交时间: 2024-01-21 20:37:05
class Solution:
def findMaximumNumber1(self, k: int, x: int) -> int:
def count(num: int) -> int:
@cache
def dfs(i: int, cnt1: int, is_limit: bool) -> int:
if i == 0:
return cnt1
res = 0
up = num >> (i - 1) & 1 if is_limit else 1
for d in range(up + 1): # 枚举要填入的数字 d
res += dfs(i - 1, cnt1 + (d == 1 and i % x == 0), is_limit and d == up)
return res
return dfs(num.bit_length(), 0, True)
# <= k 转换成 >= k+1 的数再减一
# 原理见 https://www.bilibili.com/video/BV1AP41137w7/
return bisect_left(range((k + 1) << x), k + 1, key=count) - 1
def findMaximumNumber2(self, k: int, x: int) -> int:
def count(num: int) -> int:
res = 0
i = x - 1
n = num >> i
while n:
res += (n // 2) << i
if n % 2:
mask = (1 << i) - 1
res += (num & mask) + 1
i += x
n >>= x
return res
return bisect_left(range((k + 1) << x), k + 1, key=count) - 1
def findMaximumNumber(self, k: int, x: int) -> int:
num = pre1 = 0
for i in range(((k + 1) << x).bit_length() - 1, -1, -1):
cnt = (pre1 << i) + (i // x << i >> 1)
if cnt <= k:
k -= cnt
num |= 1 << i
pre1 += (i + 1) % x == 0
return num - 1