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 <= 10000
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 :
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.
C++
// C++ program to find minimum number of steps needed // to covert 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 covert 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 // covert 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 GeeksForGeeks { private static int minOperations(int src, int target) { Set<GFG> visited = new HashSet<>(1000); LinkedList<GFG> queue = new LinkedList<GFG>(); GFG node = new GFG(src, 0); queue.offer(node); visited.add(node); while (!queue.isEmpty()) { GFG temp = queue.poll(); 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.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 covert 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 covert 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 |
Output :
2
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
0 Comments