价值和小于等于 K 的最大数字

标签: 位运算 二分查找 动态规划

难度: Medium

给你一个整数 k 和一个整数 x 。整数 num 的价值是由它的二进制表示中，从最低有效位开始，x，2x，3x，以此类推，这些位置上 设置位 的数目来计算。下面的表格包含了如何计算价值的例子。

x num Binary Representation Price
1 13 000001101 3
2 13 000001101 1
2 233 011101001 3
3 13 000001101 1
3 362 101101010 2

num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。

请你返回 最大 的廉价数字。

示例 1：

输入：k = 9, x = 1
输出：6
解释：由下表所示，6 是最大的廉价数字。
x num Binary Representation Price Accumulated Price
1 1 001 1 1
1 2 010 1 2
1 3 011 2 4
1 4 100 1 5
1 5 101 2 7
1 6 110 2 9
1 7 111 3 12

示例 2：

输入：k = 7, x = 2
输出：9
解释：由下表所示，9 是最大的廉价数字。
x num Binary Representation Price Accumulated Price
2 1 0001 0 0
2 2 0010 1 1
2 3 0011 1 2
2 4 0100 0 2
2 5 0101 0 2
2 6 0110 1 3
2 7 0111 1 4
2 8 1000 1 5
2 9 1001 1 6
2 10 1010 2 8

提示：

  • 1 <= k <= 1015
  • 1 <= x <= 8

Submission

运行时间: 138 ms

内存: 16.1 MB

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        def f(t):
            return sum((t + 1 >> i << i - 1) + max(0, ((t + 1) & ((1 << i) - 1)) - (1 << i - 1)) for i in range(x, t.bit_length() + 1, x))
        t = 1
        while f(t) <= k:
            t <<= 1
        a, b = t >> x, t - 1
        while a < b:
            t = a + b + 1 >> 1
            if f(t) > k:
                b = t - 1
            else:
                a = t
        return a

Explain

此题解采用二分搜索的方法来查找最大的廉价数字。首先，定义了一个辅助函数 f(t)，计算从1到t的所有数字的累积价值。函数 f(t) 利用位操作计算特定位上的值。初始时，将 t 设为1并不断左移，以快速逼近可能的上界，直至累积价值超过 k。接着，使用二分搜索方法在已知的上界和下界之间搜索，以确定累积价值不超过 k 的最大 t 值。

时间复杂度: O(log n * (log n) / x)

空间复杂度: O(1)

# Solution class definition
class Solution:
    # Function to find the maximum cheap number
    def findMaximumNumber(self, k: int, x: int) -> int:
        # Helper function to compute the accumulated price for numbers from 1 to t
        def f(t):
            return sum((t + 1 >> i << i - 1) + max(0, ((t + 1) & ((1 << i) - 1)) - (1 << i - 1)) for i in range(x, t.bit_length() + 1, x))
        t = 1
        # Find upper boundary where accumulated price exceeds k
        while f(t) <= k:
            t <<= 1
        a, b = t >> x, t - 1
        # Binary search within the determined range
        while a < b:
            t = a + b + 1 >> 1
            if f(t) > k:
                b = t - 1
            else:
                a = t
        return a

Explore

在函数 `f(t)` 中，表达式 `(t + 1 >> i << i - 1)` 和 `max(0, ((t + 1) & ((1 << i) - 1)) - (1 << i - 1))` 用于计算从1到t的所有数字在第i位上的贡献。表达式 `(t + 1 >> i << i - 1)` 计算的是总共有多少个完整的i位的周期，每个周期内有 `2^(i-1)` 个数字的第i位为1。第二个表达式 `max(0, ((t + 1) & ((1 << i) - 1)) - (1 << i - 1))` 计算的是在最后一个不完整的周期中超出 `2^(i-1)` 的部分，即最后一个周期中1的个数。这两者相加即得第i位对总价值的贡献。

在寻找上界时，变量t的值通过左移操作逼近的原因是为了以指数方式快速增加t的值，从而迅速找到一个使得累积价值超过k的t值。这种方法通过不断翻倍t的值（每次左移相当于乘以2），可以在对数时间内找到足够大的t。一旦找到f(t)大于k的情况，即确定了足够大的上界。

是的，在所有情况下a和b最终会相等。这是因为二分搜索的性质，每次迭代会将搜索范围缩小一半，不断地调整a或b的值直至它们相邻或者相等。当a和b相等时，`a < b` 的条件不再成立，此时的a（或b，因为此时a等于b）就是二分搜索的结果，即满足条件的最大t值。

在二分搜索中使用 `f(t) <= k` 作为更新下界a的条件是为了确保找到的是 **不超过** k的最大t值。如果使用 `f(t) < k`，则可能会错过正好使得 `f(t) = k` 的t值，这样就不能保证得到的是最大的t。使用小于等于条件保证了我们不会错过任何一个可能的解，因此可以找到确切的最大值。