Minimum number of operation required to convert number x into y

Example

Input

x = 3, y = 11

Output

3

Explanation

We can convert x into y using three operations:

1. Multiply three by 2
2. Again multiply by 2
3. Subtract one from the obtained number

Brute Force Approach

With the help of the Breadth-first search, we solve this problem. Create nodes after multiplying by two and subtracting by one. We run a BFS and generate nodes to get every possible number that may be reached from the starting integer.

1. While subtracting one from a number and if it becomes negative, there is no point in generating the next node from it.
2. Additionally, if we have previously done so, there is no need to create a number again. Thus, we keep track of a visited array.
    

Thus, we are obtaining all possible numbers reachable from starting number. In this way, we need a time complexity of O(N^2) and the space complexity for storing the visited nodes will be O(N), where N will be the nodes in the graph.

Efficient Approach

For the optimized solution, we will check for the least bit of the number. We have been given to convert x into y, but we will convert y into x as it will be an easy approach.

So, the reversed operations for y will be:

1. Divide the number by 2
2. Increment number by 1
    

Let's start with the implementation of the code.

C++ Code

/* C++ program */
#include <iostream>

using namespace std;

int main() {
    
    /* Input x and y */
    int x = 3;
    int y = 11;
    
    /* creating a variable for the number of operations performed */
    int operations = 0;
    
    /* run while loop until y != x */
    while (y != x) {
        if (y > x) {
            if (y % 2 == 0) {
                y = y/2;
                operations++;
            }
            else {
                y++;
                operations++;
            }
        }
        else if (x > y) {
            y++;
            operations++;
        }
    }
    
    cout << operations << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python Code

# Python Program

# Input x and y
x = 3;
y = 11;

# creating a variable for the number of operations performed
operations = 0;

while (y != x):
    if (y > x):
        if (y % 2 == 0):
            y = y/2;
            operations = operations+1;
        else:
            y = y+1;
            operations = operations+1;
    else:
        y = y+1;
        operations = operations+1;

print(operations);

You can also try this code with Online Python Compiler

Run Code

Input

x = 3, y = 11

Output

3

Complexities

Time complexity

O(Y-X), where X, Y is the given number in the problem.

Reason: In the worst case, we will subtract 1 from the 2 * X to obtain the number Y.

As a result, O(Y-X) is the total time complexity.

Space complexity

O(1)

Reason: No need for auxiliary space to solve the above problem.

Check out this problem - Longest Subarray With Sum K 

Frequently Asked Questions

What is the Breadth-First Search?

Breadth-first search is a searching algorithm for a tree data structure for a node that meets a certain property. Now, moving on to the nodes at the next level, it begins at the tree's root and investigates every node.

What do you mean by a simple path in a graph?

A simple path in geometry is a simple curve, precisely a continuous injective function from an actual number interval to a metric space, topological space, or, more generally. A simple path in graph theory is a path through a graph that doesn't have recurring vertices.

What is Dynamic programming?

With the use of a series of simpler subproblems, each of which is solved just once and then stored using the technique known as Dynamic Programming, which can be considered to solve such problems.

How can the longest and shortest path be determined in a graph?

The shortest path in a graph formed from G by changing each weight to its opposite is the same as the longest path between two given vertices, s, and t, in a weighted graph G. Since shortest pathways may be discovered in G, it follows the longest paths as well.

What is the best case time complexity for finding the Breadth-First Search in a Graph?

The best case time complexity for finding Breadth-First Search in a graph can be O(1) when only a single or no vertex is present in the Graph.

Conclusion

In the article, we have discussed one popular question: Minimum number of operations required to convert the number x into y. We hope this article will help you understand the concept of the Breadth-first search. Check out our other blogs on this topic:

• Data Structures and Algorithms Web Technologies
• Aptitude
• Competitive Programming
• Java
• Python
• Basic software testing and methodology
• Learn basics of Python
   

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!