Dado un número entero X, la tarea es convertir 1 en X usando las siguientes operaciones:
- Multiplica el número por 2.
- Multiplica el número por 3.
- Suma 1 al número.
La tarea es imprimir el número mínimo de operaciones necesarias para convertir 1 en X usando estas tres operaciones y también imprimir la secuencia de operaciones realizadas.
Ejemplos:
Entrada: X = 5
Salida:
3
1 3 4 5
Explicación:
Antes de cualquier operación, X = 1
1ra Operación: Multiplique el número 1 por 3, por lo tanto X = 3.
2da Operación: Sume 1 al número 3, por lo tanto X = 4 .3ra
Operación: Sume 1 al número 4, por lo tanto X = 5.
Por lo tanto, se requieren mínimo 3 operaciones y la secuencia es 1 3 4 5.Entrada: X = 20
Salida:
4
1 3 9 10 20
Explicación:
Antes de cualquier operación, X = 1
1ra Operación: Multiplique el número 1 por 3, por lo tanto X = 3.
2da Operación: Multiplique el número 3 por 3, por lo tanto X = 9.
3ra Operación: Sume 1 al número 9, por lo tanto X = 10.
4ta Operación: Multiplique el número 10 por 2, por lo tanto X = 20.
Por lo tanto, se requieren un mínimo de 4 operaciones y la secuencia es 1 3 9 10 20 .
Enfoque ingenuo: el enfoque más simple es encontrar todas las secuencias posibles de operaciones para convertir 1 en X y devolver la que tiene el número mínimo de operaciones.
Complejidad de Tiempo: O(3 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque ingenuo anterior, la idea es utilizar la programación dinámica para encontrar el número mínimo de operaciones y luego retroceder para encontrar la secuencia de operaciones requerida. A continuación se muestran los pasos:
- Inicialice dp[] para almacenar el número mínimo de operaciones para que cada índice i alcance 1 a i .
- Ahora dp[X] almacena el número mínimo de operaciones requeridas para hacer X desde 1. Completaremos la array dp[] en el enfoque ascendente . Para cualquier valor X podemos reducirlo de una de las siguientes maneras:
- Si X es divisible por 2, entonces divídalo por 2 y cuente esta operación.
- Si X es divisible por 3, entonces divídalo por 3 y cuente esta operación.
- De lo contrario, reste 1 de X.
- A partir de los pasos anteriores, la relación de recurrencia formada viene dada por:
dp[X] = min(dp[X/2] + 1, // If X is divisible by 2
dp[X/3] + 1, // If X is divisible by 3
dp[X-1] + 1)
Base Condition:
dp[1] = 0 // As no operation required when X = 1
- Después de crear la array dp[] , retroceda utilizando los valores almacenados en la array y almacene la secuencia en la lista.
- Imprime las operaciones mínimas y la secuencia almacenada en la lista.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to print the Minimum number
// of operations required to convert 1
// into X by using three given operations
void printMinOperations(int N)
{
// Initialize a DP array to store
//min operations for sub-problems
int dp[N + 1];
for(int i = 0; i < N + 1; i++)
dp[i] = N;
// Base Condition:
// No operation required
// when N is 1
dp[1] = 0;
for(int i = 2; i < N + 1; i++)
{
// Multiply the number by 2
if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
dp[i] = dp[i / 2] + 1;
// Multiply the number by 3
if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)
dp[i] = dp[i / 3] + 1;
// Add 1 to the number.
if (dp[i] > dp[i - 1] + 1)
dp[i] = dp[i - 1] + 1;
}
// Print the minimum operations
cout << dp[N] << endl;
// Initialize a list to store
// the sequence
vector<int>seq;
// Backtrack to find the sequence
while (N > 1)
{
seq.push_back(N);
// If add by 1
if(dp[N - 1] == dp[N] - 1)
N = N - 1;
// If multiply by 2
else if (N % 2 == 0 &&
dp[N / 2] == dp[N] - 1)
N = N / 2;
// If multiply by 3
else
N = N / 3;
}
seq.push_back(1);
// Print the sequence of operation
for(int i = seq.size() - 1; i >= 0; i--)
cout << seq[i] << " ";
cout << endl;
}
// Driver code
int main()
{
// Given number X
int X = 96234;
// Function call
printMinOperations(X);
}
// This code is contributed by Stream_Cipher
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the Minimum number
// of operations required to convert 1
// into X by using three given operations
static void printMinOperations(int N)
{
// Initialize a DP array to store
//min operations for sub-problems
int dp[] = new int[N + 1];
for(int i = 0; i < N + 1; i++)
dp[i] = N;
// Base Condition:
// No operation required
// when N is 1
dp[1] = 0;
for(int i = 2; i < N + 1; i++)
{
// Multiply the number by 2
if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
dp[i] = dp[i / 2] + 1;
// Multiply the number by 3
if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)
dp[i] = dp[i / 3] + 1;
// Add 1 to the number.
if (dp[i] > dp[i - 1] + 1)
dp[i] = dp[i - 1] + 1;
}
// Print the minimum operations
System.out.println(dp[N]);
// Initialize a list to store
// the sequence
Vector<Integer> seq = new Vector<Integer>();
// Backtrack to find the sequence
while (N > 1)
{
seq.add(N);
// If add by 1
if(dp[N - 1] == dp[N] - 1)
N = N - 1;
// If multiply by 2
else if (N % 2 == 0 &&
dp[N / 2] == dp[N] - 1)
N = N / 2;
// If multiply by 3
else
N = N / 3;
}
seq.add(1);
// Print the sequence of operation
for(int i = seq.size() - 1; i >= 0; i--)
System.out.print(seq.get(i) + " ");
}
// Driver code
public static void main(String args[])
{
// Given number X
int X = 96234;
// Function call
printMinOperations(X);
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 program for the above approach # Function to print the Minimum number # of operations required to convert 1 # into X by using three given operations def printMinOperations(N): # Initialize a DP array to store # min operations for sub-problems dp = [N]*(N + 1) # Base Condition: # No operation required # when N is 1 dp[1] = 0 for i in range(2, N + 1): # Multiply the number by 2 if (i % 2 == 0 and dp[i] > dp[i//2]+1): dp[i] = dp[i//2]+1 # Multiply the number by 3 if (i % 3 == 0 and dp[i] > dp[i//3]+1): dp[i] = dp[i//3]+1 # Add 1 to the number. if (dp[i] > dp[i-1]+1): dp[i] = dp[i-1] + 1 # Print the minimum operations print(dp[N], end ="\n") # Initialize a list to store # the sequence seq = [] # Backtrack to find the sequence while (N > 1): seq.append(N) # If add by 1 if dp[N-1] == dp[N] - 1: N = N-1 # If multiply by 2 elif N % 2 == 0 and dp[N//2] == dp[N] - 1: N = N//2 # If multiply by 3 else: N = N//3 seq.append(1) # Print the sequence of operation for i in reversed(seq): print(i, end =" ") # Driver Code # Given number X X = 96234 # Function Call printMinOperations(X)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the Minimum number
// of operations required to convert 1
// into X by using three given operations
static void printMinOperations(int N)
{
// Initialize a DP array to store
//min operations for sub-problems
int []dp = new int[N + 1];
for(int i = 0; i < N + 1; i++)
dp[i] = N;
// Base Condition:
// No operation required
// when N is 1
dp[1] = 0;
for(int i = 2; i < N + 1; i++)
{
// Multiply the number by 2
if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
dp[i] = dp[i / 2] + 1;
// Multiply the number by 3
if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)
dp[i] = dp[i / 3] + 1;
// Add 1 to the number.
if (dp[i] > dp[i - 1] + 1)
dp[i] = dp[i - 1] + 1;
}
// Print the minimum operations
Console.WriteLine(dp[N]);
// Initialize a list to store
// the sequence
List<int> seq = new List<int>();
// Backtrack to find the sequence
while (N > 1)
{
seq.Add(N);
// If add by 1
if(dp[N - 1] == dp[N] - 1)
N = N - 1;
// If multiply by 2
else if (N % 2 == 0 &&
dp[N / 2] == dp[N] - 1)
N = N / 2;
// If multiply by 3
else
N = N / 3;
}
seq.Add(1);
seq.Reverse();
// Print the sequence of operation
foreach(var i in seq)
{
Console.Write(i + " ");
}
}
// Driver code
public static void Main()
{
// Given number X
int X = 96234;
// Function call
printMinOperations(X);
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// JavaScript program for the above approach
// Function to print the Minimum number
// of operations required to convert 1
// into X by using three given operations
function printMinOperations(N)
{
// Initialize a DP array to store
//min operations for sub-problems
var dp = Array(N+1)
for(var i = 0; i < N + 1; i++)
dp[i] = N;
// Base Condition:
// No operation required
// when N is 1
dp[1] = 0;
for(var i = 2; i < N + 1; i++)
{
// Multiply the number by 2
if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
dp[i] = dp[i / 2] + 1;
// Multiply the number by 3
if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)
dp[i] = dp[i / 3] + 1;
// Add 1 to the number.
if (dp[i] > dp[i - 1] + 1)
dp[i] = dp[i - 1] + 1;
}
// Print the minimum operations
document.write( dp[N] + "<br>");
// Initialize a list to store
// the sequence
var seq = [];
// Backtrack to find the sequence
while (N > 1)
{
seq.push(N);
// If add by 1
if(dp[N - 1] == dp[N] - 1)
N = N - 1;
// If multiply by 2
else if (N % 2 == 0 &&
dp[N / 2] == dp[N] - 1)
N = N / 2;
// If multiply by 3
else
N = N / 3;
}
seq.push(1);
// Print the sequence of operation
for(var i = seq.length - 1; i >= 0; i--)
document.write( seq[i] + " ");
document.write("<br>");
}
// Driver code
// Given number X
var X = 96234;
// Function call
printMinOperations(X);
</script>
Producción:
14 1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por swathypanayoor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA