Work backwards: transform to . The reverse operations are halve (if even) or add . Greedy: if and is even, halve it.
If is odd, add (makes it even for halving).
If , just add . Halving is powerful: it reduces quickly. Adding is cheap but slow. Prioritize halving when possible. Why this is optimal: halving reduces by a factor of , which is exponentially faster than adding .
If is odd, you must add to make it even before halving. Once , halving would undershoot, so you switch to adding the difference.