198. Fewest Steps to a Number
Challenge1000 ms256 MBSolved by 0%
You start at the number a and want to reach b. In one step you may either
DOUBLE the current number or SUBTRACT one from it. The number may never go below zero.
Print the fewest steps needed.
This is the same breadth-first search as the grid problems, with numbers in place of cells and two moves in place of four, which is the point. The queue does not care what it is searching.
Constraints - `1 ≤ a ≤ 1000` - `1 ≤ b ≤ 1000`
Input
A single line containing two integers a and b, separated by a space.
Output
Print one integer, the fewest steps to turn a into b. Print 0 if they are already equal.
Input4 6
Output2
Noteneeds a subtraction then a doubling, so doubling first is wrong
Input2 3
Output2
Notemust go UP past the target and come back down
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.