**Introduction:**

The problem we will be heading towards is based on arithmetic operations that will be solved using some Data Structure. Arithmetic operators perform subtraction, addition, multiplication, division, modulo(‘-’,’+’,’*’,’/’,’%’) operations. We will be converting a number to another number with the help of these arithmetic operators.

Let’s understand what is the exact problem statement.

We are given an integer ‘N’. We can apply the following operations on this Integer:-

- N + N = 2 * N
- N - N = 0
- N / N = 1
- N * N = N ^ 2

We need to find the minimum number of operations as mentioned above required to convert N to M. If we can’t convert N to M, we need to return -1.

**Input: **

N = 9; M = 324

**Output: **

2

**Explanation:**

We will perform +*. Performing ‘+’ for 9 will give us 18. Then we will perform * on 18, which will give us 324. Hence, two operations are required.

**Approach:**

The ‘-’ and the ‘/’ operations are easy to handle as ‘-’ will always make the number 0, whereas ‘/’ will make the number 1.

Now, we will use Breadth-First Search to solve this question. We will initially push ‘N’ to the Queue. We will then apply all four operations on top of the queue and push it to the queue. As soon as the top of the queue becomes equal to M, we will stop our Breadth-First Search.

We will also maintain a Set to check if we have already visited the current state or not. This will help us to avoid calculating the same state again.

Also, along with the integer, we will push the String of operations we have performed to the queue.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
/*
Function to find the minimum
number of operations required
to convert N to M.
*/
string changeNtoM(int N, int M)
{
/*
If N and M are already
equal we will return
an empty String.
*/
if (N == M) {
return " ";
}
// Case where M = 0
if (M == 0) {
return "-";
}
// Initializing queue to perform BFS
queue<pair<int, string> > q;
/*
Map tp store if we have
already visited the current
State or not.
*/
unordered_map<int, bool> visited;
// Initial State
q.push({ N, "" }), visited[N] = 1;
// State where the first operation is /
q.push({ 1, "/" }), visited[1] = 1;
while (!q.empty()) {
pair<int, string> curr = q.front();
q.pop();
/*
If the top of the
queue is equal to M
We will return from here.
*/
if (curr.first == M) {
// Return answer
return cur.second;
}
//'+' operation
if (!visited[curr.first + cur.first] && curr.first + curr.first <= M) {
q.push({ curr.first + curr.first, curr.second + "+" });
visited[curr.first + curr.first] = 1;
}
// '*' operation
if (!visited[curr.first * curr.first] && curr.first * curr.first <= M) {
q.push({ curr.first * curr.first, curr.second + "*" });
visited[curr.first * curr.first] = 1;
}
}
// No valid sequence of operations exist
return "-1";
}
// Driver Code
int main()
{
int N = 9, M = 324;
string result = changeNtoM(N, M);
if (result == "-1"){
cout << result << endl;
}
else{
cout << result.length() << endl << result;
}
return 0;
}
```

**Output**

2 |

**Time Complexity:** The time complexity to solve this approach is **O(min(2log2(M – N), M – N))**

**Space Complexity: **The space complexity to solve this approach is **O((M-N)* log2(M – N))**