#3007

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Number That Sum of the Prices Is Less Than or Equal to K

Find the greatest number whose accumulated price, based on binary set bit positions, is less than or equal to k.

binary search dynamic programming bit manipulation

Problem Statement

You are given an integer k and an integer x. The price of a number num is determined by counting the set bits at positions x, 2x, 3x, etc., in its binary representation, starting from the least significant bit. This process defines the price of the number.

The accumulated price of num is the total price of all numbers from 1 to num. A number is considered cheap if its accumulated price is less than or equal to k. You are tasked with returning the greatest cheap number.

Examples

Example 1

Input: k = 9, x = 1

Output: 6

As shown in the table below, 6 is the greatest cheap number.

Example 2

Input: k = 7, x = 2

Output: 9

As shown in the table below, 9 is the greatest cheap number.

Constraints

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

Solution Approach

State Transition Dynamic Programming

Implement a state transition dynamic programming approach to calculate the accumulated price of numbers efficiently. Use the known bit manipulation rules to compute the prices for all numbers up to a given point.

Binary Search

To maximize the cheap number, employ binary search to find the greatest number such that the accumulated price does not exceed k. This step optimizes the search process.

Bit Manipulation Optimization

Leverage bit manipulation techniques to calculate the prices efficiently. Focus on the specific bit positions that impact the total price calculation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the chosen approach. A binary search combined with dynamic programming can improve the time complexity to log scale. The space complexity will vary depending on how much state is stored in memory, but it can be optimized using bit manipulation to reduce memory usage.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Binary Search + Digit DP

We notice that if $\textit{num}$ increases, the total value from $1$ to $\textit{num}$ also increases. Therefore, we can use a binary search method to find the largest cheap number.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Continue Practicing

#3117 minimum sum of values by dividing array #2035 partition array into two arrays to minimize sum difference #3003 maximize the number of partitions after operations