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

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.