Given two integers N and X, the task is to convert 1 to N using minimum operations of any of the following operations:
- Change a number (say T) into T*X. This costs one unit.
- Right rotate the number. This costs one unit.
Note: Right rotation means the last digit of the number becomes the first and all other digits get shifted rightwards. For example, 456 becomes 645. The right-shuffle operation cannot be done on single-digit integers or integers which are a multiple of 10.
Examples:
Input: N = 61, X =4
Output: 3
Explanation: The sequence of operations is as follows :
- 1 -> 4 (Using first operation -> T*X= 1 * 4 = 4) cost = 1
- 4 -> 16 (Using first operation -> T*X = 4 * 4 = 16) cost = 1
- 16 -> 61 (Using second operation -> right shuffling 16 -> 61) cost = 1
Hence, the minimum costs required to convert from initial 1 to N is 3.
Input: N = 72, X = 3
Output: 4
Explanation: The sequence of operations is as follows :
- 1 -> 3 (Using first operation -> T*X = 1*3 = 3 ) cost = 1
- 3 -> 9 (Using first operation -> T*X = 3*3 = 9) cost = 1
- 9 -> 27 (Using first operation -> T*X = 9*3 = 27) cost = 1
- 27 -> 72 (Using second operation -> right shuffling 27 -> 72) cost = 1
Hence, the minimum cost required to convert from initial 1 to N is 4.
Input: N = 5, X = 3
Output: -1
Explanation: It is impossible to reach 5.
Naive Approach: The naive approach is to try all possible combinations by performing the operations.
It can be observed that the upper limit of required operations does not exceed value N. So generate all possible values that can be formed using i operations (i in range [1, N]) and check if any of them is equal to N and update the minimum cost accordingly
Look here to generate all the possible combinations of T operations. Follow the below steps to solve this problem:
- Iterate a loop from T = 1 to N
- Iterate over all 2T combinations of possible numbers using T moves (2T because either perform type 1 or type 2 operation).
- Assign temp = 1 to store the number formed
- If the first operation is not performed
- Assign temp = temp*X
- Else, if temp > 0 and temp is not a multiple of 10
- Right rotate temp.
- If temp = N, then return T because that is the minimum cost.
- Iterate over all 2T combinations of possible numbers using T moves (2T because either perform type 1 or type 2 operation).
- If it is not possible to form the number within N steps then it cannot be formed (as mentioned earlier), so return -1.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Returns integer after one right rotatelong long right_shuffle(long long t){ // Convert int to string. auto str = to_string(t); // Rotate the string. rotate(str.begin(), str.begin() + str.size() - 1, str.end()); // Convert back to integer and return return stoll(str);}// Function to find the minimum costint minimumCoins(int n, int x){ // Iterate over number of moves. for (int t = 1; t <= n; ++t) { // Generate all 2^T combinations. for (int mask = 0; mask < (1LL << t); ++mask) { long long temp = 1; for (int i = 0; i < t; ++i) { // If current bit is off if (!(mask & (1LL << i))) { // Perform first operation temp = temp * x; } else { // If not possible to do // second operation if (temp <= 10 || temp % 10 == 0) temp = temp * x; // Perform second operation else temp = right_shuffle(temp); } } // If temp = n, t is the answer if (temp == n) return t; } } // If impossible to reach N return -1;}// Driver codeint main(){ int N = 61, X = 4; // Function call cout << minimumCoins(N, X); return 0;} |
Java
// Java program for the above approachclass GFG{ // Returns integer after one right rotate static int right_shuffle(int num) { int rev_num = 0; while(num > 0) { rev_num = rev_num * 10 + num % 10; num = num / 10; } return rev_num; } // Function to find the minimum cost static int minimumCoins(int n, int x) { // Iterate over number of moves. for (int t = 1; t <= n; ++t) { // Generate all 2^T combinations. for (int mask = 0; mask < (1 << t); ++mask) { int temp = 1; for (int i = 0; i < t; ++i) { // If current bit is off if ((mask & (1 << i)) == 0) { // Perform first operation temp = temp * x; } else { // If not possible to do // second operation if (temp <= 10 || temp % 10 == 0) temp = temp * x; // Perform second operation else temp = right_shuffle(temp); } } // If temp = n, t is the answer if (temp == n) return t; } } // If impossible to reach N return -1; } // Driver Code public static void main(String args[]) { int N = 61, X = 4; // Function call System.out.print(minimumCoins(N, X)); }}// This code is contributed by sanjoy_62. |
Python3
# python3 code to implement the approach# Returns integer after one right rotatedef right_shuffle(t): # Convert int to string. stri = str(t) # Rotate the string. stri = stri[len(stri) - 1] + stri[:-1] # Convert back to integer and return return int(stri)# Function to find the minimum costdef minimumCoins(n, x): # Iterate over number of moves. for t in range(1, n + 1): # Generate all 2^T combinations. for mask in range(0, 1 << t): temp = 1 for i in range(0, t): # If current bit is off if (not(mask & (1 << i))): # Perform first operation temp = temp * x else: # If not possible to do # second operation if (temp <= 10 or temp % 10 == 0): temp = temp * x # Perform second operation else: temp = right_shuffle(temp) # If temp = n, t is the answer if (temp == n): return t # If impossible to reach N return -1# Driver codeif __name__ == "__main__": N, X = 61, 4 # Function call print(minimumCoins(N, X))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG { // Returns integer after one right rotate static int right_shuffle(int num) { int rev_num = 0; while (num > 0) { rev_num = rev_num * 10 + num % 10; num = num / 10; } return rev_num; } // Function to find the minimum cost static int minimumCoins(int n, int x) { // Iterate over number of moves. for (int t = 1; t <= n; ++t) { // Generate all 2^T combinations. for (int mask = 0; mask < (1 << t); ++mask) { int temp = 1; for (int i = 0; i < t; ++i) { // If current bit is off if ((mask & (1 << i)) == 0) { // Perform first operation temp = temp * x; } else { // If not possible to do // second operation if (temp <= 10 || temp % 10 == 0) temp = temp * x; // Perform second operation else temp = right_shuffle(temp); } } // If temp = n, t is the answer if (temp == n) return t; } } // If impossible to reach N return -1; } // Driver Code public static void Main(string[] args) { int N = 61, X = 4; // Function call Console.WriteLine(minimumCoins(N, X)); }}// This code is contributed by phasing17 |
Javascript
//JS code to implement the approach// Returns integer after one right rotatefunction right_shuffle(t){ // Convert int to string. var stri = t.toString(); // Rotate the string. stri = stri[stri.length - 1] + stri.substring(0, stri.length - 1); // Convert back to integer and return return parseInt(stri);}// Function to find the minimum costfunction minimumCoins(n, x){ // Iterate over number of moves. for (var t = 1; t <= n; t++) { // Generate all 2^T combinations. for (var mask = 0; mask < (1 << t); mask++) { var temp = 1; for (var i = 0; i < t; i++) { // If current bit is off if (!(mask & (1 << i))) { // Perform first operation temp = temp * x; } else { // If not possible to do // second operation if (temp <= 10 || temp % 10 == 0) temp = temp * x; // Perform second operation else temp = right_shuffle(temp); } } // If temp = n, t is the answer if (temp == n) return t; } } // If impossible to reach N return -1;}// Driver codevar N = 61;var X = 4;// Function callconsole.log(minimumCoins(N, X));// This code is contributed by phasing17 |
Output
3
Time Complexity: O(N * 2N)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved efficiently using BFS based on the below idea:
- Build a graph out of the transitions. If we can go from T1 to some T2 using either one of the two operations, we can add an edge with weight = 1 from T1 to T2.
- Once the graph has been built, the minimum number of operations from 1 to N, would be the shortest distance from 1 to N in the graph.
However, since the number can be increased using the first operation, we need an upper bound to know when to stop building the graph.
- Suppose, an integer T consists of D digits. Using the second operation does not change the number of digits, and using the first operation either increases or keeps D the same.
- So now we know that the number of digits is non-decreasing. Hence, we don’t need to use any number with more digits than N, we can use 10*N as the upper limit.
Follow the below steps to solve this problem:
- Declare a distance array dis[10*N] to find the distance or minimum cost to convert 1 to N.
- Assign all the dis[i] to INF (Large Value)
- Start a BFS from node 1. In the BFS:
- If node = N, means we have reached the target. So break that call.
- If node*X < 10*N, push node*X into the queue for further usage in the BFS call.
- If node is not divisible by 10 and node>10 and right_shuffle(node)<10*N
- Push right_shuffle(node) into queue
- If reaching N (i.e. dis[N] = inf)is impossible return -1.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Returns integer after one right rotateint right_shuffle(int t){ // Convert int to string. auto str = to_string(t); // Rotate the string. rotate(str.begin(), str.begin() + str.size() - 1, str.end()); // Convert back to integer and return return stoi(str);}// Function to find the minimum costint minimumCoins(int n, int x){ // Infinity const int INF = 1e9; // Declare visited and distance arrays vector<int> dis(10 * n, INF); vector<bool> vis(10 * n, 0); // Mark 1 as visited and its distance as 0 dis[1] = 0, vis[1] = 1; queue<int> q; q.push(1); // BFS while (!q.empty()) { int curr = q.front(); q.pop(); // If 'N' is reached, stop the BFS if (curr == n) break; // First Operation if (1LL * curr * x < 10 * n && !vis[curr * x]) { vis[curr * x] = 1; q.push(curr * x); dis[curr * x] = dis[curr] + 1; } // If can't perform second operation if (curr <= 10 || curr % 10 == 0) continue; // Second operation int rt = right_shuffle(curr); if (rt < 10 * n && !vis[rt]) { vis[rt] = 1; q.push(rt); dis[rt] = dis[curr] + 1; } } // If distance infinity, N is unreachable if (dis[n] == INF) return -1; else return dis[n];}// Driver codeint main(){ int N = 61, X = 4; // Function call cout << minimumCoins(N, X); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG{// Returns integer after one right rotatestatic int right_shuffle(int t){ // Convert int to String. String str = String.valueOf(t); // Rotate the String. str = rotate(str); // Convert back to integer and return return Integer.parseInt(str);}static String rotate(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);}// Function to find the minimum coststatic int minimumCoins(int n, int x){ // Infinity int INF = (int) 1e9; // Declare visited and distance arrays int dis[] = new int[10*n]; int vis[] = new int[10*n]; Arrays.fill(dis, 0); Arrays.fill(vis, 0); // Mark 1 as visited and its distance as 0 dis[1] = 0; vis[1] = 1; Queue<Integer> q = new LinkedList<>(); q.add(1); // BFS while (!q.isEmpty()) { int curr = q.peek(); q.remove(); // If 'N' is reached, stop the BFS if (curr == n) break; // First Operation if (1 * curr * x < 10 * n && vis[curr * x]==0) { vis[curr * x] = 1; q.add(curr * x); dis[curr * x] = dis[curr] + 1; } // If can't perform second operation if (curr <= 10 || curr % 10 == 0) continue; // Second operation int rt = right_shuffle(curr); if (rt < 10 * n && vis[rt]==0) { vis[rt] = 1; q.add(rt); dis[rt] = dis[curr] + 1; } } // If distance infinity, N is unreachable if (dis[n] == INF) return -1; else return dis[n];}// Driver codepublic static void main(String[] args){ int N = 61, X = 4; // Function call System.out.print(minimumCoins(N, X));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 code to implement the approach# Returns integer after one right rotatedef right_shuffle(t): # Convert int to string. str_ = str(t) # Rotate the string. str_ = str_[-1] + str_[:len(str_) - 1] # Convert back to integer and return return int(str_)# Function to find the minimum costdef minimumCoins(n, x): # Infinity INF = 1000000000 # Declare visited and distance arrays dis = [INF for _ in range(10 * n)] vis = [0 for _ in range(10 * n)] # Mark 1 as visited and its distance as 0 dis[1] = 0 vis[1] = 1 q = [] q.append(1) # BFS while (len(q) != 0): curr = q.pop(0) # If 'N' is reached, stop the BFS if (curr == n): break # First Operation if (curr * x < 10 * n and (vis[curr * x] == 0)): vis[curr * x] = 1 q.append(curr * x) dis[curr * x] = dis[curr] + 1 # If can't perform second operation if ((curr <= 10) or (curr % 10 == 0)): continue # Second operation rt = right_shuffle(curr) if ((rt < 10 * n) and (vis[rt] == 0)): vis[rt] = 1 q.append(rt) dis[rt] = dis[curr] + 1 # If distance infinity, N is unreachable if (dis[n] == INF): return -1 else: return dis[n]# Driver codeN = 61X = 4# Function callprint(minimumCoins(N, X))# This code is contributed by phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG{ // Returns integer after one right rotate static int right_shuffle(int t) { // Convert int to string. string str = Convert.ToString(t); // Rotate the string. str = str[str.Length - 1] + str.Substring(0, str.Length - 1); // Convert back to integer and return return Convert.ToInt32(str); } // Function to find the minimum cost static int minimumCoins(int n, int x) { // Infinity int INF = 1000000000; // Declare visited and distance arrays List<int> dis = new List<int>(); for (int i = 0; i < 10 * n; i++) dis.Add(INF); List<int> vis = new List<int>(); for (int i = 0; i < 10 * n; i++) vis.Add(0); // Mark 1 as visited and its distance as 0 dis[1] = 0; vis[1] = 1; List<int> q = new List<int>(); q.Add(1); // BFS while (q.Count != 0) { int curr = q[0]; q.RemoveAt(0); // If 'N' is reached, stop the BFS if (curr == n) break; // First Operation if (curr * x < 10 * n && (vis[curr * x] == 0)) { vis[curr * x] = 1; q.Add(curr * x); dis[curr * x] = dis[curr] + 1; } // If can't perform second operation if ((curr <= 10) || (curr % 10 == 0)) continue; // Second operation int rt = right_shuffle(curr); if ((rt < 10 * n) && (vis[rt] == 0)) { vis[rt] = 1; q.Add(rt); dis[rt] = dis[curr] + 1; } } // If distance infinity, N is unreachable if (dis[n] == INF) return -1; else return dis[n]; } // Driver code public static void Main(string[] args) { int N = 61; int X = 4; // Function call Console.Write(minimumCoins(N, X)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript code to implement the approach// Returns integer after one right rotatefunction right_shuffle(t){ // Convert int to string. let str = t.toString(); // Rotate the string. str = (str.charAt(str.length - 1) + str.slice(0, -1)); // Convert back to integer and return return parseInt(str);}// Function to find the minimum costfunction minimumCoins(n, x){ // Infinity let INF = 1e9; // Declare visited and distance arrays let dis = new Array(10 * n).fill(INF); let vis = new Array(10 * n).fill(0); // Mark 1 as visited and its distance as 0 dis[1] = 0; vis[1] = 1; let q = []; q.push(1); // BFS while (q.length != 0) { let curr = q.shift(); // If 'N' is reached, stop the BFS if (curr == n) break; // First Operation if (curr * x < 10 * n && (vis[curr * x] == 0)) { vis[curr * x] = 1; q.push(curr * x); dis[curr * x] = dis[curr] + 1; } // If can't perform second operation if ((curr <= 10) || (curr % 10 == 0)) continue; // Second operation let rt = right_shuffle(curr); if ((rt < 10 * n) && (vis[rt] == 0)) { vis[rt] = 1; q.push(rt); dis[rt] = dis[curr] + 1; } } // If distance infinity, N is unreachable if (dis[n] == INF) return -1; else return dis[n];}// Driver codelet N = 61;let X = 4; // Function callconsole.log(minimumCoins(N, X));// This code is contributed by phasing17 |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
