Minimum Operations to convert X to Y

Difficulty Level Medium
Frequently asked in Amazon Factset Fanatics Fourkites JP Morgan Myntra Samsung Spotify Square
Breadth First Search GraphViews 4475

Problem Statement

The problem “Minimum Operations to convert X to Y” states that you are given two numbers X and Y, it is needed to convert X into Y using following operations:

Starting number is X. Following operations can be performed on X and on the numbers that are generated as intermediate result.

  1. multiply the number by 2.
  2. decrease the number by 1.

Find out minimum number of steps required to convert X into Y using the operations mentioned above.

Constraints: 0 < X,Y < 1000

Example

X = 3, Y = 11
3

Explanation: 3*2 = 6, 6*2 = 12, 12-1 = 11 3 steps

X = 2, Y = 10
5

Explanation: 2*2 = 4, 4-1 = 3, 3*2 = 6, 6-1 = 5, 5*2 = 10 -> 5 steps

Approach

We apply a BFS based algorithm. Then we can perform 2 operations either we multiply by 2 or subtract by 1. In this way we can reach all the numbers that can be generated using the starting number X and performing the given two operations. If any generated number is equal to input number Y is obtained. Thus we simply return the number of steps taken to generate the number Y. While generating numbers it is important to keep following points in mind:

  1. We ignore the number from inserting into BFS queue if the generated number does not satisfy the constraints.
  2. If the currently generated number has been already generated before. We simply ignore the number by not adding it to the BFS queue. A hash set is used to keep track of numbers that are generated so far.
  3. We keep track of number of operations (in a variable named level) performed to generate a number from starting number X by performing required operations.

Algorithm to find Minimum Operations to convert X to Y

  1. Create a queue for BFS traversal and insert the starting number X and it’s level into the queue. The level of starting number is 0 as number of operations required to convert X into X is 0.
  2. Create a HashSet that stores the numbers generated so far.
  3. Then begin BFS traversal.
  4. Pop a node from the queue, if node value is equal to input number Y. And return level (Minimum number of operations from X) of this node.
  5. Else, add this node into our hash set (marking it as visited).
  6. Now, multiply the popped node value by 2 and check if it is present in the set.
  7. If the number so generated is not present in the set. Thus insert the number into queue along with it’s level (level of this node generated = level of popped (parent) node + 1).
  8. Decrease the popped node value by 1 and check if it is present in the set.
  9. If the number so generated is not present in the set. Thus insert the number into queue along with it’s level (level of this node generated = level of popped (parent) node + 1).
  10. Repeat iteratively the steps 3-9 until we encounter return condition in step-4.

The Algorithm is depicted below:

Minimum Operations to convert X to Y

Code

C++ code to find Minimum Operations to convert X to Y

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* class definition to treat 
numbers generated as nodes */
class Node
{
    public:
    int num;
    int level;
    
    Node(int num,int level)
    {
        this->num = num;
        this->level = level;
    }
};

/* function to find minimum number of 
operations required to convert x into y */
int minOperation(int x,int y)
{
    queue<Node*> q;
    unordered_set <int> us;
    
    Node *node = new Node(x,0);
    q.push(node);
    
    while(!q.empty())
    {
        Node *top = q.front();
        q.pop();
        
        if(top->num == y)
        return top->level;
        
        us.insert(top->num);
        
        /* Multiplication Operation */
        if(us.find(2*top->num) == us.end())
        {
            Node *temp = new Node(2*top->num,top->level+1);
            q.push(temp);
        }
        
        /* Subtraction Operation */
        if(us.find(top->num-1) == us.end() && top->num-1 > 0)
        {
            Node *temp = new Node(top->num-1,top->level+1);
            q.push(temp);
        }
    }
}
/* Main function */
int main()
{
    int x = 2,y = 10;
    cout<<minOperation(x,y)<<endl;
    
    return 0;
}
5

Java Code to find Minimum Operations to convert X to Y

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* class definition to treat 
    numbers generated as nodes */
    static class Node
    {
        int num;
        int level;
        
        Node(int num,int level)
        {
            this.num = num;
            this.level = level;
        }
    }
    
    /* function to find minimum number of 
    operations required to convert x into y */
    static int minOperation(int x,int y)
    {
        Queue <Node> q = new LinkedList<>();
        HashSet <Integer> hs = new HashSet<Integer>();
        
        Node node = new Node(x,0);
        q.add(node);
        
        while(!q.isEmpty())
        {
            Node top = q.poll();
            
            if(top.num == y)
            return top.level;
            
            hs.add(top.num);
            
            /* Multiplication Operation */
            if(!hs.contains(2*top.num))
            {
                Node temp = new Node(2*top.num,top.level+1);
                q.add(temp);
            }
            
            /* Subtraction Operation */
            if(!hs.contains(top.num-1) && top.num-1 > 0)
            {
                Node temp = new Node(top.num-1,top.level+1);
                q.add(temp);
            }
        }
        
        return 0;
    }
    /* Main function */
  public static void main (String[] args) 
  {
      int x = 2,y = 10;
        System.out.println(minOperation(x,y));
  }
}
5

Complexity Analysis

Time Complexity

It’s hard to comment on the time complexity for finding a number using the above approach. But we can still comment on the worst time complexity. In the worst-case what can happen is we go through all the numbers present under the constraint. Even going through all the numbers, we don’t find our required number. Thus the time complexity is O(N), where N is the largest element possible under given constraints.

Space Complexity

It’s hard to comment on space complexity as well. But similar to what we did with the time complexity. So the same is true for space complexity. In the worst-case, we’ll be inserting all the elements into the queue. This makes the algorithm to take O(N) space, where N is the largest number possible under the given constraint.

Translate »