# Divide a number in k powers of 2

Example

N = 9 and K=3

4 + 4 + 1 = 9 .

What I have tried.

We can not go on dividing with 2.

We can use unbounded knapsack with array elements from 2^0 to 2^32.

If $$k>N$$, this cannot be done (as $$\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$$)
If $$k\leq N$$: Write $$N$$ in binary, and denote by $$n$$ the number of $$1$$s. We have written $$N$$ as a sum of $$n$$ powers of two (which happen to all be distinct).
1. If $$n\leq k$$, then you can always split some of the powers of two (iteratively if needed) in order to obtain $$N$$ as a sum of $$k$$ powers of two (you cannot be stuck with only terms of the form $$2^0$$ -which cannot be split- before reaching $$k$$ terms as $$k\leq N$$ by assumption).
2. If $$n>k$$, then it cannot be done. Indeed, assume it could be done, and consider the decomposition into $$k$$ powers of two. (Iteratively) merge these powers of two until you reach a binary decomposition of $$N$$. This decomposition has at most $$k$$ $$1$$s, which is absurd by uniqueness of the binary decomposition.