## Sunday, November 27, 2016

### Minimum number of operation required to convert number x into y - GeeksforGeeks

Minimum number of operation required to convert number x into y - GeeksforGeeks
Given a initial number x and two operations which are given below:
1. Multiply number by 2.
2. Subtract 1 from the number.
The task is to find out minimum number of operation required to convert number x into y using only above two operations. We can apply these operations any number of times.

The idea is to use BFS for this. We run a BFS and create nodes by multiplying with 2 and subtracting by 1, thus we can obtain all possible numbers reachable from starting number.
Important Points :
1) When we subtract 1 from a number and if it becomes < 0 i.e. Negative then there is no reason to create next node from it (As per input constraints, numbers x and y are positive).
2) Also, if we have already created a number then there is no reason to create it again. i.e. we maintain a visited array.
`int` `minOperations(``int` `x, ``int` `y)`
`{`
`    ``// To keep track of visited numbers`
`    ``// in BFS.`
`    ``set<``int``> visit;`

`    ``// Create a queue and enqueue x into it.`
`    ``queue<node> q;`
`    ``node n = {x, 0};`
`    ``q.push(n);`

`    ``// Do BFS starting from x`
`    ``while` `(!q.empty())`
`    ``{`
`        ``// Remove an item from queue`
`        ``node t = q.front();`
`        ``q.pop();`

`        ``// If the removed item is target`
`        ``// number y, return its level`
`        ``if` `(t.val == y)`
`            ``return` `t.level;`

`        ``// Mark dequeued number as visited`
`        ``visit.insert(t.val);`

`        ``// If we can reach y in one more step`
`        ``if` `(t.val*2 == y || t.val-1 == y)`
`            ``return` `t.level+1;`

`        ``// Insert children of t if not visited`
`        ``// already`
`        ``if` `(visit.find(t.val*2) == visit.end())`
`        ``{`
`            ``n.val = t.val*2;`
`            ``n.level = t.level+1;`
`            ``q.push(n);`
`        ``}`
`        ``if` `(t.val-1>=0 && visit.find(t.val-1) == visit.end())`
`        ``{`
`            ``n.val = t.val-1;`
`            ``n.level = t.level+1;`
`            ``q.push(n);`
`        ``}`
`    ``}`
`}`

Read full article from Minimum number of operation required to convert number x into y - GeeksforGeeks