Ok, here's a question my friend just sent me, ive mastered it to some extent, but am failing, so, please help a little:
Your target is to merge these blocks in such a way that one bigger number is formed. The merging takes place as follows : Two blocks of value 2 will make one block of value 4, then two block of value 4 will make one block of value 8 and so on. At any step, after merging, if there is a block left, then that block is automatically upgraded to next higher value. You need to find out the numbers of block merges required to get largest number possible.
Aim: Find the number of block merges required to get largest number possible
As a clue, my friend also told me that if the number of 2 blocks given are 5, in that case, the answer is 4 as, 5 blocks of 2s will make 2 blocks of 4 and one block of 2 will be upgraded to 4. Now 2 blocks of 4 will make one block 8 and one block of 4 will be upgraded to 8. Finally 2 blocks of 8 will make one block of 16 (which is the largest number possible). Hence number of merges required are: 2 + 1 + 1 = 4
FInding the algorithm to master seems highly impossible to me...
Given an initial $N$ blocks, let $z$ be the largest integer such that $2^z \le N$. Any number of blocks beyond a power of 2 cannot be used to increase the maximum achievable tile-value.
Therefore $z = \lfloor \log_2 (N) \rfloor$.
Now if the number of merges that takes place is $M$, then work out the first few values:
$$\begin{array} {c|c|c} N & z & M \\ \hline 1 & 0 & 0 \\ 2 \dots 3 & 1 & 1 \\ 4 \dots 7 & 2 & 1 + 2 = 3 \\ 8 \dots 15 & 3 & 1 + 2 + 4 = 7 \\ 16 \dots 31 & 4 & 1 + 2 + 4 + 8 = 15 \\ \vdots & \vdots & \vdots \\ \end{array}$$
Try to work out the pattern, it helps to look at the value of $M+1$.