Another Popcount Problem

A set bit is the real unit of this problem.

If some number $a_i$ contains bit $b$, then that bit contributes exactly $1$ to $\operatorname{popcount}(a_i)$ and costs exactly $2^b$ in the total sum. So instead of thinking about whole numbers, think about buying individual bits.

For every bit position $b$, we can use that bit in at most $k$ numbers, because each of the $k$ integers can contain bit $b$ at most once. That gives us this equivalent problem:

• there are $k$ available bits of cost $1$,
• $k$ available bits of cost $2$,
• $k$ available bits of cost $4$,
• $k$ available bits of cost $8$,
• and so on.

Every chosen bit gives score $1$. We need maximize the number of chosen bits with total cost at most $n$.

Now the greedy is forced: take cheaper bits before expensive bits. If we ever choose a bit of cost $2^b$ while some smaller-cost bit is still unused, swapping the expensive bit for the cheaper one keeps the score the same and uses no more budget. Usually it uses less. So any optimal solution can be transformed into one that takes bits in increasing cost order.

So we process costs

$$1, 2, 4, 8, \ldots$$

At cost $c$, there are $k$ available bits. With remaining budget $n$, we can afford at most $\left\lfloor \frac{n}{c} \right\rfloor$ of them, so we take

$$\min\left(k, \left\lfloor \frac{n}{c} \right\rfloor\right).$$

Add that amount to the answer and subtract its total cost from the remaining budget.

This also handles the annoying edge cases cleanly:

• If $k \ge n$, we can just take $n$ bits of cost $1$, so the answer is $n$.
• If $k=1$, this becomes choosing one number at most $n$ with maximum popcount, and the same bit-buying view still works.
• We never need to use all the budget. Leftover budget that cannot buy the next cheapest available bit is useless. Happens. Budget has skill issue.

Why the selected bits can always become actual numbers: for each bit position, we choose it at most $k$ times, so assign those copies to distinct sequence positions. Different bit positions can go into the same number without conflict. This constructs valid non-negative integers with exactly the chosen total popcount.

The number of processed bit positions is $O(\log n)$, since costs double each time. Therefore each test case runs in

$$O(\log n)$$

time and uses $O(1)$ memory.