Anton buys a piglet

Problem Author: | Feysa Bohdan
Prepared by: | Feysa Bohdan
Tutorial by: | Pavlo Tsitsei

To determine if a sequence of operations exists: if $$$x$$$ is not divisible by $$$2^k$$$, then the answer is $$$-1$$$, as there is no such sequence. Otherwise, it is always possible to create such a number. At a minimum, this can be done in $$$\frac{x}{2^k}$$$ operations each time using the second button.

To find the sequence of these operations, a greedy algorithm can be used. Let's say we have already used the first button $$$q$$$ times and $$$x$$$ has $$$n$$$ bits. Then, to determine whether we need to add $$$2^k$$$ first or continue using the first button, we need to check the $$$n-q$$$-th bit of the number $$$x$$$. If it is equal to 1, then before the operation, $$$2^k$$$ needs to be added. These actions need to be repeated until we get the number $$$x$$$.