Minimum commands to reach an value Sorry if I am doing it wrong in some way.

Some days ago I have passed trough an technical test in which I had 3 tasks to complete. The tasks were a problem and I have to write an algorithm to solve it.

One of the 3 tasks I could not complete. Really, I have absolutly no idea how to start.

I am not asking for ready algorithm here.

I'll try to reproduce here.



Command 'X': X = ( 2 * X ) - Y
Command 'Y': Y = ( 2 * Y ) - X
Initial values: X = 0, Y = 1;


Given a N number, what's the minimum of commands where X or Y reach N. Each command change it's own value.

If I send the command 'X', the value of X will be '-1', and so on

The exemple was N = -11
Commands: 'X','X','Y','X', this way X will be equal -11.

Command 'X', X = ( 2 * 0 ) - 1 = -1  , Y = 1
Command 'X', X = ( 2 * ( -1) )  - 1 = -3  , Y = 1
Command 'Y', X = -3                  , Y = ( 2 * 1 ) - (-3) = 5
Command 'X', X = ( 2 * -3 ) - 5 = -11, Y =5
Here are some thoughts about the task.


Let us start with reducing all power of 2 from N.
If $N=2^kM$ then we can first apply $$Y=2Y-0$$ $k$ times.


Now you have new task of reaching smaller number $M$ starting with $X=0$ and $Y=1$.


$X\le 0$ and $Y&gt;0$ holds after every transformation. So if $N$ is positive we will reach it with $Y$ and if $N \le 0$ we reach it with $X$.
Replacing $X$ with $X'=-X$ may help thinking.
$$ X' \to 2X'+Y $$
$$ Y \to 2Y+X' $$
looks simpler and is equivalent to the original task.
Applying one operation $k$ times we get
$$ Y \to 2^kY+(2^k-1)X' $$
Another nice representation of the operations:
$$ X' \to X'+(X'+Y)$$
$$Y \to Y + (X'+Y)$$
From 5. after $k$ steps sum of the numbers becomes $2^k$ and we actually add $2^{k-1}$ to one of numbers.
Solution. There is always only one way to reach $N$. Number of operations is $log_2N$. Imagine $N=101110001$ in binary form. Then we go from right to left and change X when there is 0 and Y when there is 1 in binary representation. In this way we finally construct $Y=101110001$ and almost inverted X=010001111. There is only one peculiarity. When we start for the first bit Y is already 1 and we need to apply X transformation instead of Y.