You are not logged in. Please login at to post your questions!


PLYNUM – Editorial




Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh




Graph, BFS


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 solution can be found here.

asked 07 Aug '18, 00:23

horsbug98's gravatar image

accept rate: 21%

edited 09 Aug '18, 15:37

admin's gravatar image

0★admin ♦♦

I didn't use this limit since the space of values was small enough already, but the path from $A$ to a larger $B$ doesn't need to cross approximately $8B/7$, since stepping from below $B$ to above by doubling to an equal number of steps away $s$, gives $2(B-3s) = (B+s) => s = B/7$. I would add 3 to that limit: 8B/7 + 3 to allow for detailed adjustment.

Thus the best path from say 4 to 91 shouldn't need to go above 107.

On further reflection, if the better option in the above analysis is to come down to $B$ from above, it makes more sense to do the subtractions before the doubling, since only half as many will be required. This simplifies all the above analysis to expecting that the best path from $A$ to a larger $B$ can be achieved without going above $B+2$.

On the lower end, there's clearly no point in going below $A/2$.


answered 07 Aug '18, 18:47

joffan's gravatar image

accept rate: 13%

edited 07 Aug '18, 21:00

How is the max no of steps required (B-A)/3 ? Please explain :) I am not able to get it from the above explanation.


answered 07 Aug '18, 13:58

harrypotter0's gravatar image

accept rate: 1%


Suppose you have two numbers 0 and 100. So according to the given problem, you can increment by 3 every time instead of using the multiplication operation(which will make the no of steps less, as you increment fast). If you increment by 3 every time, then you will take (100 - 0)/3 i.e. ~33 steps. So this is the worst case, as you can simply multiply by 2 in the intermediate numbers and reduce the no. of steps. So, the maximum number of steps will be O((B-A)/3). I hope this clears your doubt. If not, feel free to ask again. :)

(07 Aug '18, 14:33) horsbug984★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 07 Aug '18, 00:23

question was seen: 310 times

last updated: 09 Aug '18, 15:37