Skip to main content
Talentd

Maximum Number That Sum of the Prices Is Less Than or Equal to K - Solution & Explanation

MediumBinary SearchDynamic ProgrammingBit Manipulation20 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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 <= 1015
  • 1 <= x <= 8

Approach Overview

Problem Overview: Given integers k and x, every number has a price defined by how many set bits appear at bit positions that are multiples of x. The task is to find the maximum integer n such that the total price of all numbers from 1 to n is less than or equal to k.

Approach 1: Brute Force Search (O(n log n) time, O(1) space)

Iterate from 1 upward and compute the price of every number individually. For each integer, check its binary representation and count set bits only at positions where position % x == 0. Accumulate the total price and stop once the sum exceeds k. This approach directly follows the definition of the problem and is easy to implement using basic bit manipulation. The downside is performance: computing the price for every number requires scanning its bits, which makes the solution too slow when n becomes large.

Approach 2: Binary Search with Digit DP (O(log n * bits) time, O(bits) space)

The key observation: instead of evaluating each number individually, compute how many valid bits appear in the range [1, n]. Once you can quickly calculate the total price up to any n, the problem becomes finding the largest n whose total price is ≤ k. That turns the task into a classic binary search problem.

During the check step, count how many numbers in [1, n] have a set bit at each position that is a multiple of x. This can be computed using a bit counting pattern or a small dynamic programming style digit DP over the binary representation of n. For each valid bit position, determine how many numbers contribute a set bit there and add that to the total price.

Binary search runs over the possible answer range (typically up to 10^15 or higher depending on constraints). Each midpoint check computes the cumulative price using the bit counting logic. Because the number of bits in an integer is small (around 60 for 64‑bit numbers), the counting step is fast, making the overall complexity roughly O(log n * 60).

Recommended for interviews: The expected solution uses binary search combined with bit counting or digit DP. Interviewers want to see that you convert the problem into a monotonic search condition and efficiently compute the prefix price. Starting with the brute force explanation demonstrates understanding of the price definition, while the optimized binary search approach shows strong algorithmic reasoning.

Approach 1: Brute Force Search

This approach involves checking each number incrementally to determine the accumulated price. For each number, compute its price by counting set bits at positions x, 2x, 3x, etc. Keep a running total of the accumulated price and find the largest number where this total is less than or equal to k.

  • Function calculate_price calculates the price for a given number by counting set bits at positions x, 2x, etc., incrementally.
  • The main loop continues until adding the next price would exceed k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N * log(N)), where N is the largest number considered. For each number, bit positions are checked sequentially.
Space Complexity: O(1), as only a few variables are used regardless of input size.

Try this approach in the editor →

Approach 2: Dynamic Programming Search

This approach involves using dynamic programming and caching to store precomputed results for price calculation, thereby reducing redundant computations. This method is particularly helpful when re-computing the price of numbers multiple times, allowing a speed-up by avoiding recalculations.

  • Uses a dynamic programming table dp to store already computed prices for each number to avoid redundant calculations.
  • With caching, repeated access and computation times for the same numbers are reduced.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N * log(N)), but reduces redundancy through look-ups.
Space Complexity: O(N), where N is the size of the dp array.

Try this approach in the editor →

Approach 3: Binary Search + Digit DP

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

We define the left boundary of the binary search as l = 1. Since there is at least one valuable number in every 2^x + 1 numbers, and the total value does not exceed 10^{15}, we can set the right boundary of the binary search as r = 10^{18}.

Next, we perform a binary search. For each mid, we use the digit DP method to calculate the total value from 1 to mid. If the total value does not exceed k, it means mid is a cheap number, and we update the left boundary l to mid. Otherwise, we update the right boundary r to mid - 1.

Finally, we return the left boundary l.

The time complexity is O(log^2 k), and the space complexity is O(log k).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Search

Time Complexity: O(N * log(N)), where N is the largest number considered. For each number, bit positions are checked sequentially.
Space Complexity: O(1), as only a few variables are used regardless of input size.

Dynamic Programming Search

Time Complexity: O(N * log(N)), but reduces redundancy through look-ups.
Space Complexity: O(N), where N is the size of the dp array.

Binary Search + Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SearchO(n log n)O(1)Useful for understanding the price definition or when constraints are very small
Binary Search + Bit Counting / Digit DPO(log n * bits)O(bits)Best choice for large inputs; efficiently finds the maximum valid number using monotonic search

Video Solution

Maximum Number That Sum of the Prices Is Less Than or Equal to K |Brute Force |Optimal |Contest 380 • codestorywithMIK • 7,457 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.
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.
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).
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.

Ready to solve this problem?

Practice Maximum Number That Sum of the Prices Is Less Than or Equal to K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of Two Sorted Arrays

Next

Search in Rotated Sorted Array