Given two numbers A and B, the task is to find the minimum number of the following operations to transform A to B:
- Multiply the current number by 2 (i.e. replace the number X by 2X)
- Append the digit 1 to the right of the current number (i.e. replace the number X by 10X?+?1).
Print -1 if it is not possible to transform A to B.
Examples:
Input: A = 2, B = 162
Output: 4
Explanation:
Operation 1: Change A to 2*A, so A=2*2=4
Operation 2: Change A to 2*A, so A=2*4=8.
Operation 3: Change A to 10*A+1, so A=10*8+1=81
Operation 4: Change A to 2*A, so A=2*81=162Input: A = 4, B = 42
Output: -1
Approach: This problem can be solved by recursively generating all possible solutions and then choosing the minimum out of those. Now, to solve this problem, follow the below steps:
- Create a recursive function minOperation which will accept three parameters that are current number (cur), target number (B) and a map (dp) to memoise the returned result. This function will return the number of minimum operations required to transform the current number to the target number.
- Initially pass A as cur, B and a empty map dp in minOperations.
- Now in each recursive call:
- Check if cur is greater than B, if it is then return INT_MAX as it is not possible to transform the current number to B.
- Check if cur is equal to B, if it is then return 0.
- Also check if the result of this function call is already stored in map dp. If it is, then return it from there.
- Otherwise, call this function again for (cur* 2) and (cur*10+1) and return the minimum result out of these two after memoising.
- Now, if the initial call returns INT_MAX, then print -1 as it is not possible to transform A to B. Otherwise the answer is the integer returned from this function call.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find// the minimum number of operations// needed to transform A to Bint minOperations(int cur, int B, unordered_map<int, int>& dp){ // If current number // is greater than target if (cur > B) { return INT_MAX; } // if current number // is equal to the target if (cur == B) { return 0; } // If the number of minimum // operations required to // change the current number // to the target number // is already memoised if (dp.count(cur)) { return dp[cur]; } // Minimum number of operations // required if the current element // gets multiplied by 2 int ans1 = minOperations(cur * 2, B, dp); // Minimum number of operations // required if the 1 is appended to // the right of the current element int ans2 = minOperations(cur * 10 + 1, B, dp); // If it is not possible // to reach the target value // from the current element if (min(ans1, ans2) == INT_MAX) { return dp[cur] = INT_MAX; } // Returning the minimum // number of operations return dp[cur] = min(ans1, ans2) + 1;}// Driver Codeint main(){ int A = 2, B = 162; unordered_map<int, int> dp; int ans = minOperations(A, B, dp); // If A cannot be transformed to B if (ans == INT_MAX) { cout << -1; } else { cout << ans; }} |
Java
// Java code for the above approachimport java.util.HashMap;class GFG { // Function to find // the minimum number of operations // needed to transform A to B static int minOperations(int cur, int B, HashMap<Integer, Integer> dp) { // If current number // is greater than target if (cur > B) { return Integer.MAX_VALUE; } // if current number // is equal to the target if (cur == B) { return 0; } // If the number of minimum // operations required to // change the current number // to the target number // is already memoised if (dp.containsKey(cur)) { return dp.get(cur); } // Minimum number of operations // required if the current element // gets multiplied by 2 int ans1 = minOperations(cur * 2, B, dp); // Minimum number of operations // required if the 1 is appended to // the right of the current element int ans2 = minOperations(cur * 10 + 1, B, dp); // If it is not possible // to reach the target value // from the current element if (Math.min(ans1, ans2) == Integer.MAX_VALUE) { dp.put(cur, Integer.MAX_VALUE); return dp.get(cur); } // Returning the minimum // number of operations dp.put(cur, Math.min(ans1, ans2) + 1); return dp.get(cur); } // Driver Code public static void main(String args[]) { int A = 2, B = 162; HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>(); int ans = minOperations(A, B, dp); // If A cannot be transformed to B if (ans == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(ans); } }}// This code is contributed by gfgking. |
Python3
# Python 3 code for the above approachimport sys# Function to find# the minimum number of operations# needed to transform A to Bdef minOperations(cur, B, dp): # If current number # is greater than target if (cur > B): return sys.maxsize # if current number # is equal to the target if (cur == B): return 0 # If the number of minimum # operations required to # change the current number # to the target number # is already memoised if (cur in dp): return dp[cur] # Minimum number of operations # required if the current element # gets multiplied by 2 ans1 = minOperations(cur * 2, B, dp) # Minimum number of operations # required if the 1 is appended to # the right of the current element ans2 = minOperations(cur * 10 + 1, B, dp) # If it is not possible # to reach the target value # from the current element if (min(ans1, ans2) == sys.maxsize): dp[cur] = sys.maxsize return dp[cur] # Returning the minimum # number of operations dp[cur] = min(ans1, ans2) + 1 return dp[cur]# Driver Codeif __name__ == "__main__": A = 2 B = 162 dp = {} ans = minOperations(A, B, dp) # If A cannot be transformed to B if (ans == sys.maxsize): print(-1) else: print(ans) # This code is contributed by ukasp. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find // the minimum number of operations // needed to transform A to B static int minOperations(int cur, int B, Dictionary<int, int> dp) { // If current number // is greater than target if (cur > B) { return Int32.MaxValue; } // if current number // is equal to the target if (cur == B) { return 0; } // If the number of minimum // operations required to // change the current number // to the target number // is already memoised if (dp.ContainsKey(cur)) { return dp[cur]; } // Minimum number of operations // required if the current element // gets multiplied by 2 int ans1 = minOperations(cur * 2, B, dp); // Minimum number of operations // required if the 1 is appended to // the right of the current element int ans2 = minOperations(cur * 10 + 1, B, dp); // If it is not possible // to reach the target value // from the current element if (Math.Min(ans1, ans2) == Int32.MaxValue) { dp[cur] = Int32.MaxValue; return dp[cur]; } // Returning the minimum // number of operations dp[cur] = Math.Min(ans1, ans2) + 1; return dp[cur]; } // Driver Code public static void Main(string[] args) { int A = 2, B = 162; Dictionary<int, int> dp = new Dictionary<int, int>(); int ans = minOperations(A, B, dp); // If A cannot be transformed to B if (ans == Int32.MaxValue) { Console.WriteLine(-1); } else { Console.WriteLine(ans); } }}// This code is contributed by gaurav01. |
Javascript
<script> // JavaScript code for the above approach // Function to find // the minimum number of operations // needed to transform A to B function minOperations(cur, B, dp) { // If current number // is greater than target if (cur > B) { return Number.MAX_VALUE; } // if current number // is equal to the target if (cur == B) { return 0; } // If the number of minimum // operations required to // change the current number // to the target number // is already memoised if (dp[cur] != 0) { return dp[cur]; } // Minimum number of operations // required if the current element // gets multiplied by 2 let ans1 = minOperations(cur * 2, B, dp); // Minimum number of operations // required if the 1 is appended to // the right of the current element let ans2 = minOperations(cur * 10 + 1, B, dp); // If it is not possible // to reach the target value // from the current element if (Math.min(ans1, ans2) == Number.MAX_VALUE) { return dp[cur] = Number.MAX_VALUE; } // Returning the minimum // number of operations return dp[cur] = Math.min(ans1, ans2) + 1; } // Driver Code let A = 2, B = 162; let dp = new Array(100000).fill(0); let ans = minOperations(A, B, dp); // If A cannot be transformed to B if (ans == Number.MAX_VALUE) { document.write(-1); } else { document.write(ans); }// This code is contributed by Potta Lokesh </script> |
Output
4
Time Complexity: O(log2 B*log10 B)
Auxiliary Space: O(max(log2 B, log10 B))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
