You are given an integer k and an integer x. The price of a number num is calculated by the count of set bits at positions x, 2x, 3x, etc., in its binary representation, starting from the least significant bit. The following table contains examples of how price is calculated.
| 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 |
The accumulated price of num is the total price of numbers from 1 to num. num is considered cheap if its accumulated price is less than or equal to k.
Return the greatest cheap number.
Example 1:
Input: k = 9, x = 1
Output: 6
Explanation:
As shown in the table below, 6 is the greatest cheap number.
| 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 |
Example 2:
Input: k = 7, x = 2
Output: 9
Explanation:
As shown in the table below, 9 is the greatest cheap number.
| 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 |
Constraints:
1 <= k <= 10151 <= x <= 8In LeetCode #3007: Maximum Number That Sum of the Prices Is Less Than or Equal to K, the goal is to find the largest integer n such that the total "price" of numbers from 1 to n does not exceed k. The price of a number depends on specific bit positions, making bit manipulation an essential part of the solution.
A common strategy is to apply binary search on the answer. Instead of iterating through every number, we guess a candidate n and efficiently compute the total price for all numbers from 1 to n. This calculation leverages patterns in binary representation and can be implemented using digit DP or bit-counting techniques to count how many numbers contribute set bits at required positions.
If the computed price is ≤ k, we move the search range higher; otherwise, we shrink it. This combination of binary search with efficient bit counting ensures the solution remains fast even for very large values of n. The approach avoids brute force enumeration and scales well for large constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Bit Counting / Digit DP | O(log N * log N) | O(log N) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Binary search the answer.
In each step of the binary search you should calculate the number of the set bits in the <code>i<sup>th</sup></code> position. Then calculate the sum of them.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Binary search works because the total price function is monotonic as n increases. If the price for a given n exceeds k, any larger number will also exceed the limit, allowing the search space to be reduced efficiently.
Problems like #3007 reflect the type of questions asked in top tech interviews. They test understanding of binary search on the answer, bit manipulation, and optimization techniques such as digit DP.
This problem mainly relies on mathematical observations and bit manipulation rather than complex data structures. Binary search is used to explore the answer space, and digit DP or bit-counting logic helps evaluate candidate values efficiently.
The optimal approach combines binary search with efficient bit counting. Binary search is used to guess the largest valid number n, while digit DP or bit manipulation helps compute the total price from 1 to n quickly without iterating through every number.