Maximum Number That Sum of the Prices Is Less Than or Equal to K Python/Java solution

Most implementations follow the same pattern: binary search for the maximum n and a helper function that calculates the total price up to n using bit counting. This logic translates cleanly to Python, Java, C++, C#, and JavaScript because it only uses integer arithmetic and bit operations.

What is the best approach for Maximum Number That Sum of the Prices Is Less Than or Equal to K?

The optimal approach uses binary search on the answer combined with bit counting (digit DP). For a candidate number n, compute the total price contributed by all numbers from 1 to n by counting set bits at positions that are multiples of x. Because the price sum grows monotonically with n, binary search efficiently finds the largest valid value.

Is Maximum Number That Sum of the Prices Is Less Than or Equal to K asked at Google/Amazon/Meta?

Problems combining binary search with bit manipulation and prefix counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often require computing contributions of bits across ranges or applying digit DP with a monotonic condition.

What data structure is used in Maximum Number That Sum of the Prices Is Less Than or Equal to K?

The solution mainly relies on binary search and bit manipulation. Some implementations use a digit dynamic programming approach over the binary representation of numbers to count contributions efficiently.

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

The optimized solution runs in O(log n * bits), where bits is the number of bits in the integer representation (around 60 for 64-bit numbers). Each binary search step evaluates a prefix price calculation using bit counting, which scans valid bit positions.

Description Hints 2 Solution Video 1:06:24

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

Q: Is Maximum Number That Sum of the Prices Is Less Than or Equal to K easy or hard?

The problem is typically classified as Medium. The difficulty comes from recognizing that brute force enumeration is infeasible and that the prefix price function is monotonic, allowing a binary search combined with bit counting or digit DP.

Q: How to solve Maximum Number That Sum of the Prices Is Less Than or Equal to K in O(log n)?

Use binary search over the possible answer range and compute the total price for each midpoint. The price calculation counts how many numbers contribute a set bit at positions divisible by x using bit patterns or digit DP. Since each check only processes about 60 bits, the total runtime becomes O(log n).

Medium38.4% acceptance2 companies

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 <= 10¹⁵
1 <= x <= 8

Asked at 2 companies

Google Microsoft

Topics

Hints open one at a time

Hint 1

Binary search the answer.

Hint 2

In each step of the binary search you should calculate the number of the set bits in the i^th position. Then calculate the sum of them.

1:06:24

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findMaximumNumber(self, k: int, x: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

9
1

Input

7
2

Your code is saved on this device.Solution