Breadth-first search is a searching algorithm for a tree data structure for a node that meets a certain property. In this article, we will discuss one of its applications: the minimum number of operations required to convert the number x into y.

Problem Statement

You have been given numbers x and y. You must perform operations on the number x to obtain the number y. You can multiply x by two or subtract one from the number as many times as you want. You need to print the minimum number of operations required to achieve the number y.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Example

Input

x = 3, y = 11

Output

3

Explanation

We can convert x into y using three operations:

Multiply three by 2

Again multiply by 2

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.

While subtracting one from a number and if it becomes negative, there is no point in generating the next node from it.

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:

Divide the number by 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;
}

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

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.

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: