PROBLEM LINK:Author: Maksym Bevza DIFFICULTY:Cakewalk PREREQUISITES:Ad hoc, bitwise operators PROBLEM:You need to convert an integer $A$ to integer $B$, where both are positive and $B$ is a power of two. The allowed moves are the following (if the current number is $v$):
What is the minimum number of moves to do this? (it can be shown that this is always possible!) QUICK EXPLANATION:The fastest way is the following:
The number of steps this takes is the answer. EXPLANATION:We will make use of the fact that the target integer, $B$, is a power of two. First, let's notice what the operations really do. The first operation roughly "halves" $v$, and the second operation doubles $v$. Thus, it makes sense to consider the binary representation of $v$. In fact, the operations are simply the Bitwise logical shift operations! In other words, the first operation is simply a single right shift, and the second operation is a single left shift. A shift is simply an operation that "shifts" the binary representation of a number. For example, shifting the binary integer "1001101" left once results in "10011010". Note that we use a "0" for new digit places. Also, when shifting right, the rightmost digit is discarded: for example, the right shift of "1001101" and "1001100" are both "100110". It's fairly straightforward to see why the operations described in the problem statement are simply shifts. With this in mind, how do we quickly go from $A$ to $B$? Since $B$ is a power of two, it has exactly one $1$ in its binary representation. Notice that using either operation doesn't increase the number of $1$s in the binary representation of a number. Therefore, the first action we must do is to convert the initial number into one that contains a single $1$ in its binary representation (i.e. a power of two). To do this, we shift right, until it becomes a power of two. Now that our number is already a power of two, we can simply shift left or right repeatedly until it becomes equal to $B$! The answer is simply the total number of shifts in both steps combined, and it's quite easy and intuitive to see why this is the optimal solution. The following is an implementation in C++:
A somewhat faster solutionWe can use a few more bitwise tricks to compute the answer without performing the steps themselves. Notice that there are two parts in calculating the answer:
How can we calculate the number of steps required in part one? Note that the answer is simply one more than the position from the right of the second most significant bit of $A$, or zero if there isn't such a bit (i.e. $A$ is a power of two already). We can compute this value quickly if we can perform the following operation quickly:
It can be dissected into a series of the following operations:
Removing a particular bit is easy; the number
Now, how do we implement the last one? Given $v = 2^i$, we want to compute $i$. Note that $i$ is simply the number of $1$ bits in the number $v1$! But how do we count the $1$ bits in a given number? It can be done with the following pseudocode (once again, we invite the reader to see why this works):
With these, we can now extract the position of the second largest bit of a number:
Now, for the second part: assuming the current number $A$ is a power of two, how many steps do we need to convert it to $B$? This is very simple: it's just the difference between the positions of the bits of $A$ and $B$, i.e.
Time Complexity:$O(\log A + \log B)$ or $O(\log \log A + \log \log B)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 Aug '15, 13:06

Check out the shortest solution to this problem: answered 20 Aug '15, 23:15
why not editorialist ,tester, author provide such short and easy code for editorial which easy to understand as well as good to see?? thanks to harshgupta11 sharing this solution
(25 Aug '15, 14:59)

@durwasa_jec, nothing was wrong in your approach. Just some basic error which gave WA. These should be kept in mind always. There is always some precision error in C, especially with large values. The log function you use many a times return answer such as 12.999999999 etc. instead of 13. This happens many a times. A typically example illustrating this is given in the following code, http://ideone.com/3j3OmD. Since only integer part of the the logarithm was required, it can be calculated using while loop. I think the error was with the ceil and floor comparison. Try removing that. Also, instead of using log(b/a) and log(a/b), Use log(a)log(b) and vice versa. I personally suggest you to use double instead of floats whenever required. If possible avoid them. Sometimes it passes, sometimes it may give an error on some corner cases. Here is the link to my solution https://www.codechef.com/viewsolution/7642483 (python code), https://www.codechef.com/viewsolution/7637949 (c++ code). Hope it helps :). answered 18 Aug '15, 23:28

why not Editorialist ,Tester, Author provide such short and easy code for editorial which easy to understand as well as good to see?? thanks to @harshgupta11 sharing this solution HAPPY CODING answered 25 Aug '15, 15:01

here is very easy implementation https://www.codechef.com/viewsolution/7890452 less then 25 lines easy to understand thanks:) answered 25 Aug '15, 15:47

FOR BEGINNERS answered 11 Sep '16, 09:50
