Tutorialspoint.dev

Minimum number of operation required to convert number x into y

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

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
Answer = 4
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.

C++

// C++ program to find minimum number of steps needed
// to covert a number x into y with two operations
// allowed : (1) multiplication with 2 (2) subtraction
// with 1.
#include<bits/stdc++.h>
using namespace std;
  
// A node of BFS traversal
struct node
{
    int val;
    int level;
};
  
// Returns minimum number of operations
// needed to covert 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<node> 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
// covert 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<GFG> visited = new HashSet<>(1000);
        LinkedList<GFG> queue = new LinkedList<GFG>();
  
        GFG node = new GFG(src, 0);
  
        queue.offer(node);
        visited.add(node);
  
        while (!queue.isEmpty()) 
        {
            GFG temp = queue.poll();
            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.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 covert 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 covert 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


Output :

2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter