Codeforces problem B Two Buttons analysis

Problem Type : BFS , math , greedy , shortest path

Problem link: Two Buttons

this was a very interesting for me.

This problem asks us what is the minimum steps we need to reach from one given number to another given number by multiplying by 2 or  subtracting 1

i have found 2 ways to solve this problem 
       1) using bfs (hard way)
       2) simple mathematics

The hard way:

let us try to analyze 2 given test cases 

1)  4 ->6  minimum steps: 2
2) 10 ->1 minimum steps: 9

let us make a graph using the 2 test cases

if we run a simple bfs from the starring number and creates nodes by multiplying with 2 and subtracting by 1 we can get all possible numbers reachable from starting number

but we have to optimize it or we will get memory limit exceeded error on some test cases and also tle for creating all possible numbers

the thing to look here is that if we multiply a number by 2 and it becomes bigger then the number we need to reach then there is no reason to create next node for that number cause we can't reach the targeted number from that bigger number

and another thing is when we subtract 1 from a number if it becomes negative then there is no reason to create next node from it as input is two distinct integers n and m (1 ≤ n, m ≤ 10^4) 

and if we have already created a number then there is no reason to create it again

so the implementation becomes 

Now the easy way:

if input is n and m and n is the starting number and m is the targeted number

we can go from n to m or we can go from m to n both will take the same minimum steps.Its easier to go from m to n then go from n to m cause when n is bigger than m we have to subtract 1 from n to reach m. so we can try to make m smaller or equal to n