Minimize steps required to convert number N to M using arithmetic operators - Coding

Given two integers N and M, the task is to find the sequence of the minimum number of operations required to convert the number N into M such that in each operation N can be added (N = N + N), subtracted as (N = N – N), multiplied as (N = N*N), or divided as (N = N/N). If it is not possible to convert N into M then print “-1”.

Examples:

Input: N = 7, M = 392
Output: 3
+, *, +
Explanation:
Following are the operations performed:

Performing addition modifies the value of N as 7 + 7 = 14.

Performing multiplication modifies the value of N as 14*14 = 196.

Performing addition modifies the value of N as 196 + 196 = 392.

After the above sequence of moves as “+*+”, the value of N can be modified to M.

Input: N = 7, M = 9
Output: -1
Explanation: There are no possible sequence of operations to convert N to M.

Approach: The given problem can be solved using the following observations:

Subtraction operation will always result in 0 as N = N – N = 0. Similarly, division operation will always result in 1 as N = N / N = 1. Therefore, these cases can be handled easily.
For addition and multiplication, the problem can be solved using a Breadth-First Search Traversal by creating a state for each of the sequences of operations in increasing order of operation count.

The steps to solve the given problem are as follows:

Maintain a queue to store the BFS states where each state contains the current reachable integer N’ and a string representing the sequence of operations to reach N’ from N.
Initially, add a state {N, “”} representing N and sequence of operations as empty into the queue.
Add a state {1, “/”} for the division operation into the queue as well.
During the Breadth-First traversal, for each state, add two states where the 1st state will represent addition (N’ + N’) and the 2nd state will represent multiplication (N’ * N’).
Maintain an unordered map to check whether the current state is already visited during the BFS Traversal.
If the value of the current state is equal to M, then the sequence of operations obtained till M is the result. Otherwise, print “-1”.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sequence of
// minimum number of operations needed
// to convert N into M using +, -, *, /
string changeNtoM(int N, int M)
{
    // Case where N and M are same
    if (N == M) {
        return " ";
    }
 
    // Case where M = 0
    if (M == 0) {
        return "-";
    }
 
    // Stores the BFS states in a queue
    queue<pair<int, string> > q;
 
    // Stores if current state is visited
    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;
 
    // Loop for the BFS traversal
    while (!q.empty()) {
        // Stores the current BFS state
        pair<int, string> cur = q.front();
        q.pop();
 
        // If the value of current state is
        // equal to M return the stored
        // sequence of operations
        if (cur.first == M) {
            // Return answer
            return cur.second;
        }
 
        // Adding 1st state representing the
        // addition operation(N' + N')
        if (!visited[cur.first + cur.first]
            && cur.first + cur.first <= M) {
 
            // Add state into queue and
            // mark the state visited
            q.push({ cur.first + cur.first,
                     cur.second + "+" });
            visited[cur.first + cur.first] = 1;
        }
 
        // Adding 2nd state representing the
        // multiplication operation(N' * N')
        if (!visited[cur.first * cur.first]
            && cur.first * cur.first <= M) {
 
            // Add state into queue and
            // mark the state visited
            q.push({ cur.first * cur.first,
                     cur.second + "*" });
            visited[cur.first * cur.first] = 1;
        }
    }
 
    // No valid sequence of operations exist
    return "-1";
}
 
// Driver Code
int main()
{
    int N = 7, M = 392;
    string result = changeNtoM(N, M);
 
    if (result == "-1")
        cout << result << endl;
    else
        cout << result.length() << endl
             << result;
 
    return 0;
}

Java

import java.util.*;
 
class Main {
 
  // Function to find the sequence of
  // minimum number of operations needed
  // to convert N into M using +, -, *, /
  static String changeNtoM(int N, int M) 
  {
 
    // Case where N and M are same
    if (N == M) {
      return " ";
    }
 
    // Case where M = 0
    if (M == 0) {
      return "-";
    }
 
    // Stores the BFS states in a queue
    Queue<Map.Entry<Integer, String>> q = new LinkedList<>();
 
    // Stores if current state is visited
    Map<Integer, Boolean> visited = new HashMap<>();
 
    // Initial State
    q.add(new AbstractMap.SimpleEntry<>(N, ""));
    visited.put(N, true);
 
    // State where the first operation is /
    q.add(new AbstractMap.SimpleEntry<>(1, ""));
    visited.put(1, true);
 
    // Loop for the BFS traversal
    while (!q.isEmpty()) {
      // Stores the current BFS state
      Map.Entry<Integer, String> cur = q.poll();
 
      // If the value of current state is
      // equal to M return the stored
      // sequence of operations
      if (cur.getKey() == M) {
        // Return answer
        return cur.getValue();
      }
 
      // Adding 1st state representing the
      // addition operation(N' + N')
      if (!visited.containsKey(cur.getKey() + cur.getKey())
          && cur.getKey() + cur.getKey() <= M) {
 
        // Add state into queue and
        // mark the state visited
        q.add(new AbstractMap.SimpleEntry<>(cur.getKey() + cur.getKey(),
                                            cur.getValue() + "+"));
        visited.put(cur.getKey() + cur.getKey(), true);
      }
 
      // Adding 2nd state representing the
      // multiplication operation(N' * N')
      if (!visited.containsKey(cur.getKey() * cur.getKey())
          && cur.getKey() * cur.getKey() <= M) {
 
        // Add state into queue and
        // mark the state visited
        q.add(new AbstractMap.SimpleEntry<>(cur.getKey() * cur.getKey(),
                                            cur.getValue() + "*"));
        visited.put(cur.getKey() * cur.getKey(), true);
      }
    }
 
    // No valid sequence of operations exist
    return "-1";
  }
 
  // Driver Code
  public static void main(String[] args) {
    int N = 7, M = 392;
    String result = changeNtoM(N, M);
 
    if (result.equals("-1"))
      System.out.println(result);
    else
      System.out.println(result.length() + "\n" + result);
  }
}
 
// This code is contributed by aadityamaharshi21.

Python

# Python program for the above approach
 
# Function to find the sequence of
# minimum number of operations needed
# to convert N into M using +, -, *, /
def changeNtoM(N, M):
 
    # Case where N and M are same
    if N == M:
        return " "
 
    # Case where M = 0
    if M == 0:
        return "-"
 
    # Stores the BFS states in a queue
    q = []
 
    # Stores if current state is visited
    visited = {}
 
    # Initial State
    q.append([N, ""])
    visited[N] = 1
 
    # State where the first operation is /
    q.append([1, ""])
    visited[1] = 1
 
    # Loop for the BFS traversal
    while len(q) > 0:
 
        # Stores the current BFS state
        cur = q.pop(0)
 
        # If the value of current state is
        # equal to M return the stored
        # sequence of operations
        if cur[0] == M:
            # Return answer
            return cur[1]
 
        # Adding 1st state representing the
        # addition operation(N' + N')
        if (2*cur[0]) not in visited and 2*cur[0] <= M:
 
            # Add state into queue and
            # mark the state visited
            q.append([2*cur[0], cur[1] + "+"])
            visited[2*cur[0]] = 1
 
        # Adding 2nd state representing the
        # multiplication operation(N' * N')
        if (cur[0] * cur[0]) not in visited and cur[0] * cur[0] <= M:
 
            # Add state into queue and
            # mark the state visited
            q.append([cur[0] * cur[0], cur[1] + "*"])
            visited[cur[0] * cur[0]] = 1
 
    # No valid sequence of operations exist
    return "-1"
 
# Driver Code
N = 7
M = 392
result = changeNtoM(N, M)
 
if result == "-1":
    print(result)
else:
    print(len(result))
    print(result)
 
    # This code is contributed by aadityamaharshi21.

C#

using System;
using System.Collections.Generic;
 
class MainClass {
 
    // Function to find the sequence of
    // minimum number of operations needed
    // to convert N into M using +, -, *, /
    static string changeNtoM(int N, int M)
    {
        // Case where N and M are same
        if (N == M) {
            return " ";
        }
 
        // Case where M = 0
        if (M == 0) {
            return "-";
        }
 
        // Stores the BFS states in a queue
        Queue<KeyValuePair<int, string> > q
            = new Queue<KeyValuePair<int, string> >();
 
        // Stores if current state is visited
        Dictionary<int, bool> visited
            = new Dictionary<int, bool>();
 
        // Initial State
        q.Enqueue(new KeyValuePair<int, string>(N, ""));
        visited[N] = true;
 
        // State where the first operation is /
        q.Enqueue(new KeyValuePair<int, string>(1, ""));
        visited[1] = true;
 
        // Loop for the BFS traversal
        while (q.Count > 0) {
            // Stores the current BFS state
            KeyValuePair<int, string> cur = q.Dequeue();
 
            // If the value of current state is
            // equal to M return the stored
            // sequence of operations
            if (cur.Key == M) {
                // Return answer
                return cur.Value;
            }
 
            // Adding 1st state representing the
            // addition operation(N' + N')
            if (!visited.ContainsKey(cur.Key + cur.Key)
                && cur.Key + cur.Key <= M) {
 
                // Add state into queue and
                // mark the state visited
                q.Enqueue(new KeyValuePair<int, string>(
                    cur.Key + cur.Key, cur.Value + "+"));
                visited[cur.Key + cur.Key] = true;
            }
 
            // Adding 2nd state representing the
            // multiplication operation(N' * N')
            if (!visited.ContainsKey(cur.Key * cur.Key)
                && cur.Key * cur.Key <= M) {
 
                // Add state into queue and
                // mark the state visited
                q.Enqueue(new KeyValuePair<int, string>(
                    cur.Key * cur.Key, cur.Value + "*"));
                visited[cur.Key * cur.Key] = true;
            }
        }
 
        // No valid sequence of operations exist
        return "-1";
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 7, M = 392;
        string result = changeNtoM(N, M);
        if (result == "-1")
            Console.WriteLine(result);
        else
            Console.WriteLine(result.Length + "\n"
                              + result);
    }
}

Javascript

// JavaScript program for the above approach
 
// Function to find the sequence of
// minimum number of operations needed
// to convert N into M using +, -, *, /
function changeNtoM(N, M)
{
 
    // Case where N and M are same
    if (N == M) {
        return " ";
    }
 
    // Case where M = 0
    if (M == 0) {
        return "-";
    }
 
    // Stores the BFS states in a queue
    let q = [];
 
    // Stores if current state is visited
    let visited = new Map();
 
    // Initial State
    q.push([N, "" ]);
    visited.set(N, 1);
 
    // State where the first operation is /
    q.push([1, ""]);
    visited.set(1, 1);
 
    // Loop for the BFS traversal
    while (q.length > 0) {
 
        // Stores the current BFS state  
        let cur = q.shift();
         
        // If the value of current state is
        // equal to M return the stored
        // sequence of operations
        if (cur[0] == M) {
            // Return answer
            return cur[1];
        }
 
        // Adding 1st state representing the
        // addition operation(N' + N')
        if (!visited.has((2*cur[0])) && 2*cur[0]<= M) {
 
            // Add state into queue and
            // mark the state visited
            q.push([2*cur[0], cur[1] + "+"]);
            visited.set((cur[0] + cur[0]), 1);
        }
 
        // Adding 2nd state representing the
        // multiplication operation(N' * N')
        if (!visited.has((cur[0]* cur[0])) && cur[0] * cur[0] <= M) {
 
            // Add state into queue and
            // mark the state visited
            q.push([cur[0] * cur[0], cur[1] + "*" ]);
            visited.set((cur[0]* cur[0]), 1);
        }
    }
 
    // No valid sequence of operations exist
    return "-1";
}
 
// Driver Code
let N = 7;
let M = 392;
let result = changeNtoM(N, M);
 
if (result == "-1")
    console.log(result);
else{
    console.log(result.length);
    console.log(result);    
}
 
// The code is contributed by Nidhi goel

Output:

3
+*+

Time Complexity: O(min(2^log_²^{(M – N)}, M – N))
Auxiliary Space: O((M-N)* log₂(M – N))

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Minimize steps to change N to power of 2 by deleting or appending any digit
Kth largest factor of number N
Count of numbers in range [L, R] having sum of digits of its square equal to square of sum of digits
Maximize the largest number K such that bitwise and of K till N is 0
Check whether each Array element can be reduced to minimum element by replacing it with remainder with some X

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11