1074. Getting the Display Back to the Target

A display shows the number start. Two buttons are available: DOUBLE, which replaces the number by twice itself, and DECREMENT, which replaces it by one less.

Print the fewest button presses that turn start into target.

start 2, target 3 -> 2 double to 4, decrement to 3 start 5, target 8 -> 2 decrement to 4, double to 8 start 3, target 10 -> 3 double to 6, decrement to 5, double to 10 start 1024, target 1 -> 1023 decrement all the way down

Note the third route. Doubling twice from 3 reaches 12 and then needs two decrements, which is four presses; the decrement has to fall BETWEEN the two doublings, where it is worth 2 rather than 1.

## What most people try first

Breadth first search forwards from start. The trouble is deciding when to stop: doubling can overshoot arbitrarily far before decrementing back, so the search space has no obvious bound. With a bound of four times the larger value it works and is the brute force this problem was checked against for values under 3000. At 10^9 it is hopeless.

## Run the problem backwards

Reverse the two buttons. Going from target back towards start, DOUBLE becomes HALVE, usable only when the number is even, and DECREMENT becomes INCREMENT.

ops = 0 while target > start: if target is odd: target += 1 else: target /= 2 ops += 1 answer = ops + (start - target)

## Why each backward step is forced or dominant

When target is ODD, it cannot have been produced by a doubling, since doubling always gives an even number. So the last press must have been a decrement, and the backward step is an increment. No choice is made at all.

When target is EVEN and larger than start, both backward moves are available. Halving is never worse, and here is why. Any backward route that increments some number of times before halving must increment an EVEN number of times, because after an odd number of increments the number is odd and cannot be halved. And two increments followed by a halving,

t -> t+1 -> t+2 -> (t+2)/2 = t/2 + 1 three presses

reaches the same place as halving and then incrementing,

t -> t/2 -> t/2 + 1 two presses

So every pair of increments before a halving can be replaced by a single increment after it, saving one press. Repeating until no increment precedes a halving leaves the greedy route, and it is never longer.

## Once you are at or below start

Only decrements remain going forward, which is start - target presses. Doubling would move away from the target and every double would then have to be undone by at least as many decrements, so it never helps below start.

## Why forward search is so much worse

The forward branching factor is 2 with no natural bound; the backward one is 1 whenever the number is odd and is settled by the argument above when it is even. Turning a problem around so that its moves become forced is worth trying whenever one direction has a divide in it, and it is the same reasoning that makes #1053 scan its digits right to left.

## Overflow

target + 1 reaches 10^9 + 1, inside the signed 32 bit limit of 2147483647. Nothing here overflows 32 bits, and the count is at most about 10^9 when start is far above target, which also fits. This is one of the problems where reaching for 64 bits is harmless and unnecessary.

## Cost

Time O(log target + max(0, start - target)). Space O(1).

Constraints - `1 ≤ start ≤ 1000000000` - `1 ≤ target ≤ 1000000000`