Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Brute Force Approach
5.
Efficient Approach
5.1.
C++ Code
5.2.
Python Code
5.3.
Input
5.4.
Output
6.
Complexities
6.1.
Time complexity
6.2.
Space complexity
7.
Frequently Asked Questions
7.1.
What is the Breadth-First Search?
7.2.
What do you mean by a simple path in a graph?
7.3.
What is Dynamic programming?
7.4.
How can the longest and shortest path be determined in a graph?
7.5.
What is the best case time complexity for finding the Breadth-First Search in a Graph?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimum number of operation required to convert number x into y

Author Manan Singhal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

Introduction

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:

  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.

Breadth-first search

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

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.

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:

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!

Previous article
Minimum Number of Removals to Make a Mountain Array - Part 2
Next article
Maximize the sum of the product of two arrays at corresponding indexes by reversing at most one subarray of the first array
Live masterclass