Dados dos números enteros N y X , la tarea es convertir 1 a N usando operaciones mínimas de cualquiera de las siguientes operaciones:
- Cambie un número (digamos T ) a T*X . Esto cuesta una unidad.
- Gire a la derecha el número. Esto cuesta una unidad.
Nota: la rotación a la derecha significa que el último dígito del número se convierte en el primero y todos los demás dígitos se desplazan hacia la derecha. Por ejemplo, 456 se convierte en 645. La operación de barajar a la derecha no se puede realizar con números enteros de un solo dígito ni con números enteros que sean múltiplos de 10.
Ejemplos:
Entrada: N = 61, X =4
Salida: 3
Explicación: La secuencia de operaciones es la siguiente:
- 1 -> 4 (Usando la primera operación -> T*X= 1 * 4 = 4) costo = 1
- 4 -> 16 (Usando la primera operación -> T*X = 4 * 4 = 16) costo = 1
- 16 -> 61 (Usando la segunda operación -> barajar a la derecha 16 -> 61) costo = 1
Por lo tanto, los costos mínimos requeridos para convertir de 1 inicial a N son 3 .
Entrada: N = 72, X = 3
Salida: 4
Explicación: La secuencia de operaciones es la siguiente:
- 1 -> 3 (usando la primera operación -> T*X = 1*3 = 3) costo = 1
- 3 -> 9 (Usando la primera operación -> T*X = 3*3 = 9) costo = 1
- 9 -> 27 (Usando la primera operación -> T*X = 9*3 = 27) costo = 1
- 27 -> 72 (Usando la segunda operación -> barajar a la derecha 27 -> 72) costo = 1
Por lo tanto, el costo mínimo requerido para convertir de 1 inicial a N es 4 .
Entrada: N = 5, X = 3
Salida: -1
Explicación: Es imposible llegar a 5.
Enfoque ingenuo: El enfoque ingenuo consiste en probar todas las combinaciones posibles realizando las operaciones.
Se puede observar que el límite superior de operaciones requeridas no excede el valor N. Así que genere todos los valores posibles que se pueden formar usando i operaciones ( i en el rango [1, N] ) y verifique si alguno de ellos es igual a N y actualizar el costo mínimo en consecuencia
Mire aquí para generar todas las combinaciones posibles de operaciones T. Siga los pasos a continuación para resolver este problema:
- Iterar un ciclo de T = 1 a N
- Iterar sobre todas las 2 T combinaciones de números posibles usando T movimientos (2 Tporque realiza una operación de tipo 1 o de tipo 2).
- Asigne temp = 1 para almacenar el número formado
- Si no se realiza la primera operación
- Asignar temperatura = temperatura*X
- De lo contrario, si temp > 0 y temp no es un múltiplo de 10
- Temperatura de giro a la derecha .
- Si temp = N , entonces devuelva T porque ese es el costo mínimo.
- Iterar sobre todas las 2 T combinaciones de números posibles usando T movimientos (2 Tporque realiza una operación de tipo 1 o de tipo 2).
- Si no es posible formar el número en N pasos, entonces no se puede formar (como se mencionó anteriormente), así que devuelva -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Returns integer after one right rotate
long 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 cost
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 < (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 code
int main()
{
int N = 61, X = 4;
// Function call
cout << minimumCoins(N, X);
return 0;
}
Java
// Java program for the above approach
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
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 rotate def 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 cost def 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 code if __name__ == "__main__": N, X = 61, 4 # Function call print(minimumCoins(N, X)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using 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 rotate
function 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 cost
function 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 code
var N = 61;
var X = 4;
// Function call
console.log(minimumCoins(N, X));
// This code is contributed by phasing17
Producción
3
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando BFS según la siguiente idea:
- Construye un gráfico a partir de las transiciones . Si podemos pasar de T1 a algún T2 usando cualquiera de las dos operaciones, podemos agregar un borde con peso = 1 de T1 a T2 .
- Una vez construido el gráfico, el número mínimo de operaciones de 1 a N , sería la distancia más corta de 1 a N en el gráfico .
Sin embargo, dado que el número se puede aumentar usando la primera operación, necesitamos un límite superior para saber cuándo dejar de construir el gráfico.
- Supongamos que un entero T consta de D dígitos. Usar la segunda operación no cambia el número de dígitos, y usar la primera operación aumenta o mantiene D igual.
- Ahora sabemos que el número de dígitos no es decreciente. Por lo tanto, no necesitamos usar ningún número con más dígitos que N , podemos usar 10*N como límite superior.
Siga los pasos a continuación para resolver este problema:
- Declare una array de distancia dis[10*N] para encontrar la distancia o el costo mínimo para convertir 1 en N.
- Asigne todos los dis[i] a INF (Valor grande)
- Inicie un BFS desde el Node 1. En el BFS:
- Si node = N , significa que hemos alcanzado el objetivo. Así que rompe esa llamada.
- Si node*X < 10*N , inserte node*X en la cola para su uso posterior en la llamada BFS.
- Si el Node no es divisible por 10 y Node>10 y right_shuffle(Node)<10*N
- Empuje right_shuffle (Node) en la cola
- Si llegar a N (es decir , dis[N] = inf ) es imposible, devuelve -1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Returns integer after one right rotate
int 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 cost
int 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 code
int main()
{
int N = 61, X = 4;
// Function call
cout << minimumCoins(N, X);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG{
// Returns integer after one right rotate
static 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 cost
static 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 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 shikhasingrajput
Python3
# Python3 code to implement the approach # Returns integer after one right rotate def 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 cost def 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 code N = 61 X = 4 # Function call print(minimumCoins(N, X)) # This code is contributed by phasing17
C#
// C# code to implement the approach
using 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 rotate
function 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 cost
function 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 code
let N = 61;
let X = 4;
// Function call
console.log(minimumCoins(N, X));
// This code is contributed by phasing17
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)