Another Popcount Problem — Deon Nicholas

Problem

Given two integers $n$ and $k$ $(1 \leq n, k \leq 10^6)$ , construct a sequence $a_1, a_2, \ldots, a_k$ with $\sum a_i \leq n$ maximizing the total number of $1$ -bits across all the $a_i$ (the total popcount).

Output that maximum.

Initial Observations

Binary.
Make all $1$ 's?
$(111\ldots1) \times k$ ?
Greedy.

IdeaGreedily use all-ones numbers, packed as evenly as possibleAC

First thoughts: if some $a_i$ has $b$ one-bits, you clearly want it to be as small as possible while keeping those $b$ bits.

Key Observation

Any $a_i$ with $b$ one-bits can be replaced by the smallest number with $b$ one-bits — the "all ones" number $2^b - 1$ . The popcount is unchanged and the sum only shrinks, which can never hurt: it leaves more room under $n$ to squeeze in more bits elsewhere. We use this implicitly throughout.

As a reminder, the numbers $2^b - 1$ are exactly the ones that look like a run of $1$ 's in binary:

b = 1:   2^1 - 1  =  1   =  1
b = 2:   2^2 - 1  =  3   =  11
b = 3:   2^3 - 1  =  7   =  111
b = 4:   2^4 - 1  =  15  =  1111

Problem Transformation

I didn't do this explicitly while solving, but the observation above really flips the problem: for a given popcount, how small can the sum be? If it fits under $n$ , that popcount is achievable.

For example, $13 = 1101_2$ and $7 = 111_2$ both contribute $3$ to the popcount, but $7$ is smaller — and the slack might buy another bit (with $n = 13$ : taking $13$ spends the whole budget for $3$ bits, while $[7, 1]$ gets $4$ bits with budget to spare).

Key Observation

In an optimal solution, we can assume every $a_i$ is of the form $2^{b_i} - 1$ for some $b_i \geq 0$ .

Examine Examples

This problem is almost easier to see by example than to explain rigorously. Take $n = 6, k = 2$ : $[5, 1]$ has sum $6$ and $3$ bits; $[7]$ doesn't use both slots; but $[3, 3]$ has sum $6$ and $4$ bits — the best. Playing with a few of these suggests the winning shape: all-ones numbers, packed as evenly as possible.

Should you ever hold a $1$ and a $7$ when you could hold $3$ and $3$ instead? It seems you never really want one number to be much bigger than another. We can prove this with an exchange argument:

Key Observation

Writing each $a_i = 2^{b_i} - 1$ , we can assume $|b_i - b_j| \leq 1$ for all $i, j$ : the bit-counts are as balanced as possible.

Proof.

Suppose $b_j \geq b_i + 2$ . Move one bit from the big number to the small one: $b_j \to b_j - 1$ , $b_i \to b_i + 1$ . The popcount is unchanged, and the sum changes (the $-1$ 's cancel) by

\left(2^{b_i+1} + 2^{b_j-1}\right) - \left(2^{b_i} + 2^{b_j}\right) = 2^{b_i} - 2^{b_j-1} < 0,

since $b_j - 1 \geq b_i + 1$ . So balancing strictly decreases the sum at equal popcount — always a good trade.

∎

This is the main insight. All the $b_i$ differ by at most one, so there is some level $b^*$ where every item has $b^*$ bits except for a few upgraded to $b^* + 1$ . Greedily, $b^*$ should be the largest level at which $k$ items even fit:

Key Observation

Let $b^*$ be the largest $b$ with $(2^b - 1) \cdot k \leq n$ — equivalently $b^* = \lfloor \log_2(n/k + 1) \rfloor$ . In an optimal solution every item has $b^*$ bits, except some that have $b^* + 1$ .

Key Question

How many items get the extra bit?

Greedy again: give every item $b^*$ bits, then upgrade items one at a time while the budget lasts. Upgrading one item from $2^{b^*}-1$ to $2^{b^*+1}-1$ increases the sum by exactly $2^{b^*}$ . So with $\text{leftover} = n - k(2^{b^*}-1)$ still unspent, the number of upgrades is $\lfloor \text{leftover} / 2^{b^*} \rfloor$ . (This is automatically less than $k$ — if all $k$ items could be upgraded, $b^* + 1$ would contradict the maximality of $b^*$ .)

Write It Out

The rest is writing the formulas out carefully.

Algorithm

# largest b with (2^b - 1) * k <= n — increment rather than take logs
b = 0
while (2**(b+1) - 1) * k <= n:
    b += 1
 
leftover = n - k * (2**b - 1)
upgrades = leftover // (2**b)        # each extra bit costs 2^b
 
print(k * b + upgrades)

Implementation notes: no logarithms needed — incrementing $b$ is simpler and avoids floating point. Use 64-bit integers for the products.

Generate and Test

The first greedy ideas here are relatively obvious and obviously correct — the work was checking the mechanics, not finding alternatives.

Review

The answer is $k \cdot b^* + \lfloor (n - k(2^{b^*}-1)) / 2^{b^*} \rfloor$ , where $b^*$ is the largest $b$ with $(2^b-1)k \leq n$ . The path:

Use all-ones numbers. Any value can be replaced by $2^b - 1$ with the same popcount and a smaller sum — equivalently, flip the problem: minimize the sum for a given popcount. [1][2]
Balance the bit-counts. An exchange argument (move a bit from a big number to a small one) shows all $b_i$ can differ by at most one. [3]
Pick the highest level that fits: $b^*$ = largest $b$ with $(2^b - 1)k \leq n$ ; everyone gets $b^*$ bits. [4]
Spend the leftover on upgrades at $2^{b^*}$ apiece — maximality of $b^*$ guarantees fewer than $k$ of them.

(My accepted submission.)

References

Problem-solving techniques used:

Generate and Test

Easy enough that the first greedy ideas are obviously correct — don't spend time inventing alternatives, just run with it.

Problem Transformation

Given a number of bits, minimize their sum — a flip of the problem (arguably also a way of working backwards). I never framed it explicitly; I just kept trying to shrink the sum, and that assumption drove the next few insights.

Examine Examples

Playing with a few small cases leads to the same insights.

Write It Out

The ending required a bit of math — powers of two, potentially logarithms, edge cases. Not hard, but it needed careful bookkeeping.

Topics:

Math
Binary / powers of 2
Greedy
Constructive algorithms / proof by construction