Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
Given a number A, you have to reach another number B using the minimum number of operations, given you can only perform the following operations:-
1) Decrement the current number by 1
2) Increment the current number by 3
3) Multiply the current number by 2
We can simply consider this as a graph problem. We can consider A as a node in a graph and start a BFS from that node till we reach B. Here each node will have three outgoing edges.
We can consider this problem as a graph problem. Here each number will represent a node in the graph. Each node will have three outgoing edges. We can first start BFS from node A till we reach node B. The three nodes outgoing nodes from a node numbered N will be N-1, N+3 and N*2. But the graph now has infinite number of nodes. However we can limit the range of the node numbering with a simple observation that we don’t need to go below 0 and above B + (B-A)/3. In the worst case we can reach B from A in (B-A)/3 steps, since we can increment by 3 in each step. Again from B + (B-A)/3, we can reach B in (B-A)/3 steps decrementing by 1 each time, since it is the only way of decrementing a number. So, going upto B + (B-A)/3 from A and then decrementing by 1 for (B-A)/3 times is as good as incrementing A to B in (B-A)/3 steps. So we can limit the range of nodes from 0 to B+(B-A)/3.
If B is less than A, then decrementing by 1 in each step is the only way to reach B from A. So it will take (A-B) steps.
The time complexity of this algorithm is proportional to the number of vertices and edges in the graph. In the worst case the no of vertices and edges is (B + (B-A)/3) * 3 = O(B), thus worst case time for BFS will be O(B) i.e. linear time.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.