Minimum number of operation required to convert number x into y
Given a initial number x and two operations which are given below:
- Multiply number by 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.
Constraints:
1 <= x, y <= 1000
Example:
Input : x = 4, y = 7 Output : 2 We can transform x into y using following two operations. 1. 4*2 = 8 2. 8-1 = 7 Input : x = 2, y = 5 Output : 4 We can transform x into y using following four operations. 1. 2*2 = 4 2. 4-1 = 3 3. 3*2 = 6 4. 6-1 = 5 Answer = 4 Note that other sequences of two operations would take more operations.
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 :
- 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).
- Also, if we have already created a number then there is no reason to create it again. i.e. we maintain a visited array.
Implementation:
C++
// C++ program to find minimum number of steps needed // to convert a number x into y with two operations // allowed : (1) multiplication with 2 (2) subtraction // with 1. #include <bits/stdc++.h> using namespace std; // A node of BFS traversal struct node { int val; int level; }; // Returns minimum number of operations // needed to convert x into y using BFS 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); } } } // Driver code int main() { int x = 4, y = 7; cout << minOperations(x, y); return 0; } |
Java
// Java program to find minimum // number of steps needed to // convert a number x into y // with two operations allowed : // (1) multiplication with 2 // (2) subtraction with 1. import java.util.HashSet; import java.util.LinkedList; import java.util.Set; class GFG { int val; int steps; public GFG( int val, int steps) { this .val = val; this .steps = steps; } } public class w3wiki { private static int minOperations( int src, int target) { Set<Integer> visited = new HashSet<>( 1000 ); LinkedList<GFG> queue = new LinkedList<GFG>(); GFG node = new GFG(src, 0 ); queue.offer(node); while (!queue.isEmpty()) { GFG temp = queue.poll(); if (visited.contains(temp.val)) { continue ; } visited.add(temp.val); if (temp.val == target) { return temp.steps; } int mul = temp.val * 2 ; int sub = temp.val - 1 ; // given constraints if (mul > 0 && mul < 1000 ) { GFG nodeMul = new GFG(mul, temp.steps + 1 ); queue.offer(nodeMul); } if (sub > 0 && sub < 1000 ) { GFG nodeSub = new GFG(sub, temp.steps + 1 ); queue.offer(nodeSub); } } return - 1 ; } // Driver code public static void main(String[] args) { // int x = 2, y = 5; int x = 4 , y = 7 ; GFG src = new GFG(x, y); System.out.println(minOperations(x, y)); } } // This code is contributed by Rahul |
Python3
# Python3 program to find minimum number of # steps needed to convert a number x into y # with two operations allowed : # (1) multiplication with 2 # (2) subtraction with 1. import queue # A node of BFS traversal class node: def __init__( self , val, level): self .val = val self .level = level # Returns minimum number of operations # needed to convert x into y using BFS def minOperations(x, y): # To keep track of visited numbers # in BFS. visit = set () # Create a queue and enqueue x into it. q = queue.Queue() n = node(x, 0 ) q.put(n) # Do BFS starting from x while ( not q.empty()): # Remove an item from queue t = q.get() # If the removed item is target # number y, return its level if (t.val = = y): return t.level # Mark dequeued number as visited visit.add(t.val) # If we can reach y in one more step if (t.val * 2 = = y or t.val - 1 = = y): return t.level + 1 # Insert children of t if not visited # already if (t.val * 2 not in visit): n.val = t.val * 2 n.level = t.level + 1 q.put(n) if (t.val - 1 > = 0 and t.val - 1 not in visit): n.val = t.val - 1 n.level = t.level + 1 q.put(n) # Driver code if __name__ = = '__main__' : x = 4 y = 7 print (minOperations(x, y)) # This code is contributed by PranchalK |
C#
// C# program to find minimum // number of steps needed to // convert a number x into y // with two operations allowed : // (1) multiplication with 2 // (2) subtraction with 1. using System; using System.Collections.Generic; public class GFG { public int val; public int steps; public GFG( int val, int steps) { this .val = val; this .steps = steps; } } public class w3wiki { private static int minOperations( int src, int target) { HashSet<GFG> visited = new HashSet<GFG>(1000); List<GFG> queue = new List<GFG>(); GFG node = new GFG(src, 0); queue.Add(node); visited.Add(node); while (queue.Count != 0) { GFG temp = queue[0]; queue.RemoveAt(0); visited.Add(temp); if (temp.val == target) { return temp.steps; } int mul = temp.val * 2; int sub = temp.val - 1; // given constraints if (mul > 0 && mul < 1000) { GFG nodeMul = new GFG(mul, temp.steps + 1); queue.Add(nodeMul); } if (sub > 0 && sub < 1000) { GFG nodeSub = new GFG(sub, temp.steps + 1); queue.Add(nodeSub); } } return -1; } // Driver code public static void Main(String[] args) { // int x = 2, y = 5; int x = 4, y = 7; GFG src = new GFG(x, y); Console.WriteLine(minOperations(x, y)); } } // This code is contributed by aashish1995 |
Javascript
// JavaScript program to find minimum number of // steps needed to convert a number x into y // with two operations allowed : // (1) multiplication with 2 // (2) subtraction with 1. // A node of BFS traversal class node { constructor(val, level) { this .val = val; this .level = level; } } // Returns minimum number of operations // needed to convert x into y using BFS function minOperations(x, y) { // To keep track of visited numbers // in BFS. const visit = new Set(); // Create a queue and enqueue x into it. const q = []; const n = new node(x, 0); q.push(n); // Do BFS starting from x while (q.length > 0) { // Remove an item from queue const t = q.shift(); // If the removed item is target // number y, return its level if (t.val == y) { return t.level; } // Mark dequeued number as visited visit.add(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.has(t.val * 2)) { n.val = t.val * 2; n.level = t.level + 1; q.push(Object.assign({}, n)); } if (t.val - 1 >= 0 && !visit.has(t.val - 1)) { n.val = t.val - 1; n.level = t.level + 1; q.push(Object.assign({}, n)); } } } // Driver code const x = 4; const y = 7; console.log(minOperations(x, y)); // This code is contributed by lokeshpotta20. |
2
Optimized solution:
In the second approach, we will check the least most bit of the number and take a decision according to the value of that bit.
Instead of converting x into y, we will convert y into x and will reverse the operations which will take the same number of operations as converting x into y.
So, reversed operations for y will be:
- Divide number by 2
- Increment number by 1
Implementation:
C++14
#include <iostream> using namespace std; int min_operations( int x, int y) { // If both are equal then return 0 if (x == y) return 0; // Check if conversion is possible or not if (x <= 0 && y > 0) return -1; // If x > y then we can just increase y by 1 // Therefore return the number of increments required if (x > y) return x - y; // If last bit is odd // then increment y so that we can make it even if (y & 1) return 1 + min_operations(x, y + 1); // If y is even then divide it by 2 to make it closer to // x else return 1 + min_operations(x, y / 2); } // Driver code signed main() { cout << min_operations(4, 7) << endl; return 0; } |
C
#include <stdio.h> int min_operations( int x, int y) { // If both are equal then return 0 if (x == y) return 0; // Check if conversion is possible or not if (x <= 0 && y > 0) return -1; // If x > y then we can just increase y by 1 // Therefore return the number of increments required if (x > y) return x - y; // If last bit is odd // then increment y so that we can make it even if (y & 1) return 1 + min_operations(x, y + 1); // If y is even then divide it by 2 to make it closer to // x else return 1 + min_operations(x, y / 2); } // Driver code signed main() { printf ( "%d" , min_operations(4, 7)); return 0; } // This code is contributed by Rohit Pradhan |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { static int minOperations( int x, int y) { // If both are equal then return 0 if (x == y) return 0 ; // Check if conversion is possible or not if (x <= 0 && y > 0 ) return - 1 ; // If x > y then we can just increase y by 1 // Therefore return the number of increments // required if (x > y) return x - y; // If last bit is odd // then increment y so that we can make it even if (y % 2 != 0 ) return 1 + minOperations(x, y + 1 ); // If y is even then divide it by 2 to make it // closer to x else return 1 + minOperations(x, y / 2 ); } public static void main(String[] args) { System.out.println(minOperations( 4 , 7 )); } } // This code is contributed by Shobhit Yadav |
Python3
def min_operations(x, y): # If both are equal then return 0 if x = = y: return 0 # Check if conversion is possible or not if x < = 0 and y > 0 : return - 1 # If x > y then we can just increase y by 1 # Therefore return the number of increments required if x > y: return a - b # If last bit is odd # then increment y so that we can make it even if y & 1 = = 1 : return 1 + min_operations(x, y + 1 ) # If y is even then divide it by 2 to make it closer to x else : return 1 + min_operations(x, y / / 2 ) # Driver code print (min_operations( 4 , 7 )) |
C#
using System; class GFG { static int min_operations( int x, int y) { // If both are equal then return 0 if (x == y) return 0; // Check if conversion is possible or not if (x <= 0 && y > 0) return -1; // If x > y then we can just increase y by 1 // Therefore return the number of increments // required if (x > y) return x - y; // If last bit is odd // then increment y so that we can make it even if (y % 2 == 1) return 1 + min_operations(x, y + 1); // If y is even then divide it by 2 to make it // closer to // x else return 1 + min_operations(x, y / 2); } // Driver code public static int Main() { Console.WriteLine(min_operations(4, 7)); return 0; } } // This code is contributed by Taranpreet |
Javascript
<script> function min_operations(x,y) { // If both are equal then return 0 if (x == y) return 0; // Check if conversion is possible or not if (x <= 0 && y > 0) return -1; // If x > y then we can just increase y by 1 // Therefore return the number of increments required if (x > y) return x - y; // If last bit is odd // then increment y so that we can make it even if (y & 1) return 1 + min_operations(x, y + 1); // If y is even then divide it by 2 to make it closer to // x else return 1 + min_operations(x, y / 2); } // Driver code document.write(min_operations(4, 7)); // This code is contributed by Taranpreet </script> |
2
Time complexity:O(Y-X), where X, Y is the given number in the problem.
Space complexity: O(1), since no extra space used.
The optimized solution is contributed by BurningTiles.
Contact Us