# Minimize Steps Required to Convert Number N to M.

Soumya Agrawal
Last Updated: May 13, 2022

## 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:-

1. N + N = 2 * N
2. N - N = 0
3. N / N = 1
4. 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 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

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))

## FAQs

1. What is the Time and Space complexity of the approach used?
The time complexity of the above approach is O(min(2log2(M – N), M – N))
The space complexity of the above approach is O((M-N)* log2(M – N))

2. Why are we maintaining the Set?
We will maintain the Set to check if we have already visited the current state or not. This will help us to avoid calculating the same state again.

## Key Takeaways:

In this blog, we have covered the following things:

1. The approach to solving this question.
2. Then we implemented the approach.

If you want to learn more about Graphs and practice some questions requiring you to take your basic knowledge on Graphs a notch higher, you can visit our Guided Path for Graphs

Also, you can use CodeStudio for various DSA questions typically asked in interviews for more practice.

Happy Coding!!!