Dados cuatro números enteros N, X, P y Q , la tarea es encontrar el costo mínimo para convertir N en 1 mediante las siguientes dos operaciones:
- Restar 1 de N con costo como P .
- Divide N entre X (si N es divisible por X), con coste Q.
Ejemplos:
Entrada: N = 5, X = 2, P = 2, Q = 3
Salida: 7
Explicación:
Operación 1: 5 – 1 -> costo = 2
Operación 2: 4 / 2 -> costo = 3
Operación 3: 2 – 1 -> costo = 2
El costo total mínimo es 2 + 3 + 2 = 7.Entrada: N = 6, X = 6, P = 2, Q = 1
Salida: 1
Explicación:
Operación 1: 6/6 con costo = 1, entonces ese sería el mínimo.
Enfoque: este problema se puede resolver utilizando el enfoque codicioso . A continuación las observaciones:
- Si x = 1, entonces la respuesta es (N – 1) * P .
- De lo contrario, si N es menor que X , entonces solo es posible disminuir el número en 1, por lo que la respuesta es (N – 1) * P.
- De lo contrario, tome la primera operación hasta que N no sea divisible por X.
- Elija la segunda operación de manera óptima comparando la primera y la segunda operación, es decir, si podemos realizar la primera operación de manera que el costo de reducir N a 1 sea mínimo, de lo contrario, elija la segunda operación.
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 find the minimum cost
// to reduce the integer N to 1
// by the given operations
int min_cost(int n, int x, int p, int q)
{
// Check if x is 1
if (x == 1) {
// Print the answer
cout << (n - 1) * p << endl;
return 0;
}
// Prestore the answer
int ans = (n - 1) * p;
int pre = 0;
// Iterate till n exists
while (n > 1) {
// Divide N by x
int tmp = n / x;
if (tmp < 0)
break;
pre += (n - tmp * x) * p;
// Reduce n by x
n /= x;
// Add the cost
pre += q;
// Update the answer
ans = min(ans,
pre + (n - 1) * p);
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
// Initialize the variables
int n = 5, x = 2, p = 2, q = 3;
// Function call
cout << min_cost(n, x, p, q);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum cost
// to reduce the integer N to 1
// by the given operations
static int min_cost(int n, int x,
int p, int q)
{
// Check if x is 1
if (x == 1)
{
// Print the answer
System.out.println((n - 1) * p);
return 0;
}
// Prestore the answer
int ans = (n - 1) * p;
int pre = 0;
// Iterate till n exists
while (n > 1)
{
// Divide N by x
int tmp = n / x;
if (tmp < 0)
break;
pre += (n - tmp * x) * p;
// Reduce n by x
n /= x;
// Add the cost
pre += q;
// Update the answer
ans = Math.min(ans,
pre + (n - 1) * p);
}
// Return the answer
return ans;
}
// Driver code
public static void main(String[] args)
{
// Initialize the variables
int n = 5, x = 2, p = 2, q = 3;
// Function call
System.out.println(min_cost(n, x, p, q));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the minimum cost # to reduce the integer N to 1 # by the given operations def min_cost(n, x, p, q): # Check if x is 1 if (x == 1): # Print the answer print((n - 1) * p) return 0 # Prestore the answer ans = (n - 1) * p pre = 0 # Iterate till n exists while (n > 1): # Divide N by x tmp = n // x if (tmp < 0): break pre += (n - tmp * x) * p # Reduce n by x n //= x # Add the cost pre += q # Update the answer ans = min(ans, pre + (n - 1) * p) # Return the answer return ans # Driver Code if __name__ == '__main__': # Initialize the variables n = 5; x = 2; p = 2; q = 3; # Function call print(min_cost(n, x, p, q)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum cost
// to reduce the integer N to 1
// by the given operations
static int min_cost(int n, int x,
int p, int q)
{
// Check if x is 1
if (x == 1)
{
// Print the answer
Console.WriteLine((n - 1) * p);
return 0;
}
// Prestore the answer
int ans = (n - 1) * p;
int pre = 0;
// Iterate till n exists
while (n > 1)
{
// Divide N by x
int tmp = n / x;
if (tmp < 0)
break;
pre += (n - tmp * x) * p;
// Reduce n by x
n /= x;
// Add the cost
pre += q;
// Update the answer
ans = Math.Min(ans,
pre + (n - 1) * p);
}
// Return the answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Initialize the variables
int n = 5, x = 2, p = 2, q = 3;
// Function call
Console.WriteLine(min_cost(n, x, p, q));
}
}
// This code is contributed by princiraj1992
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum cost
// to reduce the integer N to 1
// by the given operations
function min_cost(n, x, p, q) {
// Check if x is 1
if (x == 1) {
// Print the answer
document.write((n - 1) * p + "<br>");
return 0;
}
// Prestore the answer
let ans = (n - 1) * p;
let pre = 0;
// Iterate till n exists
while (n > 1) {
// Divide N by x
let tmp = Math.floor(n / x);
if (tmp < 0)
break;
pre += (n - tmp * x) * p;
// Reduce n by x
n = Math.floor(n / x)
// Add the cost
pre += q;
// Update the answer
ans = Math.min(ans,
pre + (n - 1) * p);
}
// Return the answer
return ans;
}
// Driver Code
// Initialize the variables
let n = 5, x = 2, p = 2, q = 3;
// Function call
document.write(min_cost(n, x, p, q));
// This code is contributed by Potta Lokesh
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)