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

• Difficulty Level : Medium
• Last Updated : 24 Aug, 2022

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 <= 1000

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
Note that other sequences of two operations
would take more operations.```

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.

Implementation:

## C++

 `// C++ program to find minimum number of steps needed``// to convert 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 convert 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``// convert 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);` `        ``while` `(!queue.isEmpty()) {``            ``GFG temp = queue.poll();``            ``if``(visited.contains(temp.val)) {``              ``continue``;``            ``}``            ``visited.add(temp.val);` `            ``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 convert 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 convert 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`

## C#

 `// C# program to find minimum``// number of steps needed to``// convert a number x into y``// with two operations allowed :``// (1) multiplication with 2``// (2) subtraction with 1.``using` `System;``using` `System.Collections.Generic;` `public` `class` `GFG {``    ``public` `int` `val;``    ``public` `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)``    ``{` `        ``HashSet visited = ``new` `HashSet(1000);``        ``List queue = ``new` `List();` `        ``GFG node = ``new` `GFG(src, 0);` `        ``queue.Add(node);``        ``visited.Add(node);` `        ``while` `(queue.Count != 0) {``            ``GFG temp = queue;``            ``queue.RemoveAt(0);``            ``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.Add(nodeMul);``            ``}``            ``if` `(sub > 0 && sub < 1000) {``                ``GFG nodeSub = ``new` `GFG(sub, temp.steps + 1);``                ``queue.Add(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);``        ``Console.WriteLine(minOperations(x, y));``    ``}``}` `// This code is contributed by aashish1995`

Output

`2`

This article is contributed by Vipin Khushu. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Optimized solution:

In the second approach, we will check the least most bit of the number and take a decision according to the value of that bit.

Instead of converting x into y, we will convert y into x and will reverse the operations which will take the same number of operations as converting x into y.

So, reversed operations for y will be:

1. Divide number by 2
2. Increment number by 1

Implementation:

## C++14

 `#include ``using` `namespace` `std;` `int` `min_operations(``int` `x, ``int` `y) {` `    ``// If both are equal then return 0``    ``if` `(x == y)``        ``return` `0;` `    ``// Check if conversion is possible or not``    ``if` `(x <= 0 && y > 0)``        ``return` `-1;` `    ``// If x > y then we can just increase y by 1``    ``// Therefore return the number of increments required``    ``if` `(x > y)``        ``return` `x - y;` `    ``// If last bit is odd``    ``// then increment y so that we can make it even``    ``if` `(y & 1)``        ``return` `1 + min_operations(x, y + 1);` `    ``// If y is even then divide it by 2 to make it closer to``    ``// x``    ``else``        ``return` `1 + min_operations(x, y / 2);``}` `// Driver code``signed` `main() {``    ``cout << min_operations(4, 7) << endl;``    ``return` `0;``}`

## C

 `#include ` `int` `min_operations(``int` `x, ``int` `y)``{` `    ``// If both are equal then return 0``    ``if` `(x == y)``        ``return` `0;` `    ``// Check if conversion is possible or not``    ``if` `(x <= 0 && y > 0)``        ``return` `-1;` `    ``// If x > y then we can just increase y by 1``    ``// Therefore return the number of increments required``    ``if` `(x > y)``        ``return` `x - y;` `    ``// If last bit is odd``    ``// then increment y so that we can make it even``    ``if` `(y & 1)``        ``return` `1 + min_operations(x, y + 1);` `    ``// If y is even then divide it by 2 to make it closer to``    ``// x``    ``else``        ``return` `1 + min_operations(x, y / 2);``}` `// Driver code``signed` `main()``{``    ``printf``(``"%d"``, min_operations(4, 7));``    ``return` `0;``}` `// This code is contributed by Rohit Pradhan`

## Java

 `/*package whatever //do not write package name here */``import` `java.io.*;` `class` `GFG``{``    ``static` `int` `minOperations(``int` `x, ``int` `y)``    ``{``      ` `        ``// If both are equal then return 0``        ``if` `(x == y)``            ``return` `0``;` `        ``// Check if conversion is possible or not``        ``if` `(x <= ``0` `&& y > ``0``)``            ``return` `-``1``;` `        ``// If x > y then we can just increase y by 1``        ``// Therefore return the number of increments``        ``// required``        ``if` `(x > y)``            ``return` `x - y;` `        ``// If last bit is odd``        ``// then increment y so that we can make it even``        ``if` `(y % ``2` `!= ``0``)``            ``return` `1` `+ minOperations(x, y + ``1``);` `        ``// If y is even then divide it by 2 to make it``        ``// closer to x``        ``else``            ``return` `1` `+ minOperations(x, y / ``2``);``    ``}` `    ``public` `static` `void` `main(String[] args)``    ``{``        ``System.out.println(minOperations(``4``, ``7``));``    ``}``}` `// This code is contributed by Shobhit Yadav`

## Python3

 `def` `min_operations(x, y):``    ``# If both are equal then return 0``    ``if` `x ``=``=` `y:``        ``return` `0` `    ``# Check if conversion is possible or not``    ``if` `x <``=` `0` `and` `y > ``0``:``        ``return` `-``1` `    ``# If x > y then we can just increase y by 1``    ``# Therefore return the number of increments required``    ``if` `x > y:``        ``return` `a``-``b` `    ``# If last bit is odd``    ``# then increment y so that we can make it even``    ``if` `y & ``1` `=``=` `1``:``        ``return` `1``+``min_operations(x, y``+``1``)` `    ``# If y is even then divide it by 2 to make it closer to x``    ``else``:``        ``return` `1``+``min_operations(x, y``/``/``2``)`  `# Driver code``print``(min_operations(``4``, ``7``))`

## C#

 `using` `System;``class` `GFG {` `  ``static` `int` `min_operations(``int` `x, ``int` `y)``  ``{` `    ``// If both are equal then return 0``    ``if` `(x == y)``      ``return` `0;` `    ``// Check if conversion is possible or not``    ``if` `(x <= 0 && y > 0)``      ``return` `-1;` `    ``// If x > y then we can just increase y by 1``    ``// Therefore return the number of increments``    ``// required``    ``if` `(x > y)``      ``return` `x - y;` `    ``// If last bit is odd``    ``// then increment y so that we can make it even``    ``if` `(y % 2 == 1)``      ``return` `1 + min_operations(x, y + 1);` `    ``// If y is even then divide it by 2 to make it``    ``// closer to``    ``// x``    ``else``      ``return` `1 + min_operations(x, y / 2);``  ``}` `  ``// Driver code``  ``public` `static` `int` `Main()``  ``{``    ``Console.WriteLine(min_operations(4, 7));``    ``return` `0;``  ``}``}` `// This code is contributed by Taranpreet`

## Javascript

 ``

Output

`2`

The optimized solution is contributed by BurningTiles. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

My Personal Notes arrow_drop_up