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

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.

Constraints:
1 <= x, y <= 10000

Example:

```Input : x = 4, y = 7
Output : 2
We can transform x into y using following
two operations.
1. 4*2  = 8
2. 8-1  = 7

Input  : x = 2, y = 5
Output : 4
We can transform x into y using following
four operations.
1. 2*2  = 4
2. 4-1   = 3
3. 3*2  = 6
4. 6-1   = 5
Answer = 4
Note that other sequences of two operations
would take more operations.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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.

## C++

 `// C++ program to find minimum number of steps needed ` `// to covert a number x into y with two operations ` `// allowed : (1) multiplication with 2 (2) subtraction ` `// with 1. ` `#include ` `using` `namespace` `std; ` ` `  `// A node of BFS traversal ` `struct` `node ` `{ ` `    ``int` `val; ` `    ``int` `level; ` `}; ` ` `  `// Returns minimum number of operations ` `// needed to covert x into y using BFS ` `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 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); ` `        ``} ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `x = 4, y = 7; ` `    ``cout << minOperations(x, y); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find minimum  ` `// number of steps needed to ` `// covert a number x into y  ` `// with two operations allowed :  ` `// (1) multiplication with 2  ` `// (2) subtraction with 1. ` ` `  `import` `java.util.HashSet; ` `import` `java.util.LinkedList; ` `import` `java.util.Set; ` ` `  `class` `GFG  ` `{ ` `    ``int` `val; ` `    ``int` `steps; ` ` `  `    ``public` `GFG(``int` `val, ``int` `steps)  ` `    ``{ ` `        ``this``.val = val; ` `        ``this``.steps = steps; ` `    ``} ` `} ` ` `  `public` `class` `GeeksForGeeks ` `{ ` `    ``private` `static` `int` `minOperations(``int` `src,  ` `                                     ``int` `target)  ` `    ``{ ` ` `  `        ``Set visited = ``new` `HashSet<>(``1000``); ` `        ``LinkedList queue = ``new` `LinkedList(); ` ` `  `        ``GFG node = ``new` `GFG(src, ``0``); ` ` `  `        ``queue.offer(node); ` `        ``visited.add(node); ` ` `  `        ``while` `(!queue.isEmpty())  ` `        ``{ ` `            ``GFG temp = queue.poll(); ` `            ``visited.add(temp); ` ` `  `            ``if` `(temp.val == target) ` `            ``{ ` `                ``return` `temp.steps; ` `            ``} ` ` `  `            ``int` `mul = temp.val * ``2``; ` `            ``int` `sub = temp.val - ``1``; ` ` `  `            ``// given constraints ` `            ``if` `(mul > ``0` `&& mul < ``1000``)  ` `            ``{ ` `                ``GFG nodeMul = ``new` `GFG(mul, temp.steps + ``1``); ` `                ``queue.offer(nodeMul); ` `            ``} ` `            ``if` `(sub > ``0` `&& sub < ``1000``)  ` `            ``{ ` `                ``GFG nodeSub = ``new` `GFG(sub, temp.steps + ``1``); ` `                ``queue.offer(nodeSub); ` `            ``} ` `        ``} ` `        ``return` `-``1``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``// int x = 2, y = 5; ` `        ``int` `x = ``4``, y = ``7``; ` `        ``GFG src = ``new` `GFG(x, y); ` `        ``System.out.println(minOperations(x, y)); ` `    ``} ` `} ` ` `  `// This code is contributed by Rahul `

## Python3

 `# Python3 program to find minimum number of  ` `# steps needed to covert a number x into y  ` `# with two operations allowed :  ` `# (1) multiplication with 2  ` `# (2) subtraction with 1.  ` `import` `queue ` ` `  `# A node of BFS traversal  ` `class` `node: ` `    ``def` `__init__(``self``, val, level): ` `        ``self``.val ``=` `val  ` `        ``self``.level ``=` `level ` ` `  `# Returns minimum number of operations  ` `# needed to covert x into y using BFS  ` `def` `minOperations(x, y): ` `     `  `    ``# To keep track of visited numbers  ` `    ``# in BFS.  ` `    ``visit ``=` `set``()  ` ` `  `    ``# Create a queue and enqueue x into it.  ` `    ``q ``=` `queue.Queue() ` `    ``n ``=` `node(x, ``0``)  ` `    ``q.put(n)  ` ` `  `    ``# Do BFS starting from x  ` `    ``while` `(``not` `q.empty()): ` `         `  `        ``# Remove an item from queue  ` `        ``t ``=` `q.get()  ` ` `  `        ``# If the removed item is target  ` `        ``# number y, return its level  ` `        ``if` `(t.val ``=``=` `y): ` `            ``return` `t.level  ` ` `  `        ``# Mark dequeued number as visited  ` `        ``visit.add(t.val)  ` ` `  `        ``# If we can reach y in one more step  ` `        ``if` `(t.val ``*` `2` `=``=` `y ``or` `t.val ``-` `1` `=``=` `y):  ` `            ``return` `t.level``+``1` ` `  `        ``# Insert children of t if not visited  ` `        ``# already  ` `        ``if` `(t.val ``*` `2` `not` `in` `visit): ` `            ``n.val ``=` `t.val ``*` `2` `            ``n.level ``=` `t.level ``+` `1` `            ``q.put(n) ` `        ``if` `(t.val ``-` `1` `>``=` `0` `and` `t.val ``-` `1` `not` `in` `visit): ` `            ``n.val ``=` `t.val ``-` `1` `            ``n.level ``=` `t.level ``+` `1` `            ``q.put(n) ` ` `  `# Driver code  ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``x ``=` `4` `    ``y ``=` `7` `    ``print``(minOperations(x, y)) ` ` `  `# This code is contributed by PranchalK `

Output :

`2`

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

This article is attributed to GeeksforGeeks.org

## tags:

Graph BFS Graph BFS

code

load comments