How can binary search help with the problem 'Maximum Number That Sum of the Prices Is Less Than or Equal to K'?

Binary search is used to efficiently narrow down the range of possible answers and find the greatest number whose accumulated price is less than or equal to k.

What is the role of state transition dynamic programming in this problem?

State transition dynamic programming helps optimize the calculation of accumulated prices, allowing you to compute them efficiently without recalculating the prices for each number repeatedly.

How does bit manipulation affect the solution for 'Maximum Number That Sum of the Prices Is Less Than or Equal to K'?

Bit manipulation is used to compute the price of a number by checking the positions of set bits, which can be done efficiently through bitwise operations.

What is the time complexity of solving the 'Maximum Number That Sum of the Prices Is Less Than or Equal to K' problem?

The time complexity depends on the approach you take, but using binary search combined with dynamic programming can reduce it to O(log N) for the search and O(N) for the dynamic programming calculation.

What are common mistakes when solving 'Maximum Number That Sum of the Prices Is Less Than or Equal to K'?

Common mistakes include not optimizing the solution with binary search, incorrectly implementing bit manipulation, and overlooking edge cases in the problem constraints.

#3007

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x ， 2x ， 3x 等位置处设置位的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。 x num Binary Representation Price 1 13 0 0 0 0 0 1 1 0 1 …

二分查找动态规划位运算

题目描述

给你一个整数 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 <= 10¹⁵
1 <= x <= 8

lightbulb

解题思路

方法一：二分查找 + 数位 DP

我们注意到，如果 $\textit{num}$ 增大，数字 $1$ 到 $\textit{num}$ 的总价值也会增大。因此，我们可以使用二分查找的方法找到最大的廉价数字。

我们定义二分查找的左边界 $l = 1$ ，由于每 $2^x + 1$ 个数中至少有一个数字是有价值的，而总价值不超过 $10^15$ ，因此我们可以设定二分查找的右边界 $r = 10^{18}$ 。

接下来，我们进行二分查找，对于每一个 $\textit{mid}$ ，我们使用数位 DP 的方法计算出 $1$ 到 $\textit{mid}$ 的总价值，如果总价值不超过 $k$ ，则说明 $\textit{mid}$ 是一个廉价数字，我们将左边界 $l$ 更新为 $\textit{mid}$ ，否则我们将右边界 $r$ 更新为 $\textit{mid} - 1$ 。

最后，我们返回左边界 $l$ 即可。

时间复杂度 $O(\log^2 k)$ ，空间复杂度 $O(\log k)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        @cache
        def dfs(pos, limit, cnt):
            if pos == 0:
                return cnt
            ans = 0
            up = (self.num >> (pos - 1) & 1) if limit else 1
            for i in range(up + 1):
                ans += dfs(pos - 1, limit and i == up, cnt + (i == 1 and pos % x == 0))
            return ans

        l, r = 1, 10**18
        while l < r:
            mid = (l + r + 1) >> 1
            self.num = mid
            v = dfs(mid.bit_length(), True, 0)
            dfs.cache_clear()
            if v <= k:
                l = mid
            else:
                r = mid - 1
        return l

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding the trade-offs between binary search and dynamic programming for optimization.
question_mark
Ability to apply bit manipulation in a dynamic programming context.
question_mark
Familiarity with binary search as a method to limit the range of potential solutions.

warning

常见陷阱

外企场景

error
Overcomplicating the bit manipulation logic for price calculations.
error
Failing to optimize the search by using binary search efficiently.
error
Not handling edge cases, such as when k is very small or very large.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjusting the price calculation for different bit positions.
arrow_right_alt
Optimizing the approach for varying sizes of k and x.
arrow_right_alt
Applying this method in problems with different price calculation rules.

help

常见问题

外企场景

继续练习

#3117 划分数组得到最小的值之和 #2035 将数组分成两个数组并最小化数组和的差 #3003 执行操作后的最大分割数量