Minimize Steps Required to Convert Number N to M.

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

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