Considering the opposite operations, we have the following equivalent problem:

Find the minimum number of operations of the following three types to change \(Y\) to \(X\):

• Type \(1\) : Add \(1\) to \(Y\)
• Type \(2\) : Subtract \(1\) from \(Y\)
• Type \(3\) : Divide \(Y\) by \(2\) (only if \(Y\) is divisible by \(2\))

Here, it is obvious that Type \(1\) and Type \(2\) does not appear consecutively.
Also, instead of adding \(1\) \(k (k \ge 2)\) times and then dividing by \(2\), we can add \(1\) \(k-2\) times, divide by \(2\), and then add \(1\) once, so that the number of operations is fewer (and the same applies for subtraction). Thus, we can see that we don’t have to perform Type \(1\) or Type \(2\) consecutively, except for after the last operation of Type \(3\).
Conversely, if \(Y = y\) after the last operation of Type \(3\), the number of remaining operations is determined to \(|X - y\).

With the observations above, consider the following recursive function:

\(\mathrm{solve}(y)\) : Answer for \(Y = y\)
\(\mathrm{solve}(y) = \)

• If \(y = 1\) : \(|X - y|\)
• If \(y\) is odd but not \(1\) : \(\min(|X - y|, \mathrm{solve}(\frac{y + 1}{2}) + 2, \mathrm{solve}(\frac{y - 1}{2}) + 2)\)
• If \(y\) is even : \(\min(|X - y|, \mathrm{solve}(\frac{y}{2}) + 1)\)

Memorize this by \(y\) and call \(\mathrm{solve}(Y)\), and we obtain the answer.

Now let’s consider the time complexity.
Consider the number of \(y\) in \(\mathrm{solve}(y)\) that originates from \(\mathrm{solve}(Y)\).
If we regard the execution of \(\mathrm{solve}(Y)\) as Level-\(0\) recursion, then \(y\) in Level-\(d\) recursion satisfies:

• \(y \ge \frac{\frac{\frac{Y - 1}{2} - 1}{2} - 1}{2}_\ddots\) (\(d\) fractions) \( = \frac{Y}{2^d} - \sum_{i = 1}^d \frac{1}{2^d} \gt \frac{Y}{2^d} - 1\) (If the recursion is repeated with \(\mathrm{solve}(\frac{y - 1}{2})\))
• \(y \le \frac{\frac{\frac{Y + 1}{2} + 1}{2} + 1}{2}_\ddots\) (\(d\) fractions) \( = \frac{Y}{2^d} + \sum_{i = 1}^d \frac{1}{2^d} \lt \frac{Y}{2^d} + 1\) (If the recursion is repeated with \(\mathrm{solve}(\frac{y + 1}{2})\))

Therefore, for each level, at most \(2\) (constant) kinds of \(y\) is called.
Since there are no more than \(O(\log(Y))\) levels, the total time complexity is \(O(\log(Y))\) if we use an \(O(1)\) hash map.