Minimum number of operation required to convert number x into y - GeeksforGeeks

Minimum number of operation required to convert number x into y - GeeksforGeeks
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.

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.

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

        }

    }

}

Read full article from Minimum number of operation required to convert number x into y - GeeksforGeeks