Dada una array arr[] , la tarea es convertirla en una array no decreciente agregando números primos a los elementos de la array de modo que la suma de los números primos agregados sea la mínima posible.
Ejemplos:
Entrada: arr[] = {2, 1, 5, 4, 3}
Salida: 7
Explicación:
{2, 1 , 5, 4, 3 } -> {2, 3 , 5, 6, 6 }
Cambiando el 2 segundo elemento de la array a 3 (1 + 2), el cuarto elemento de la array a 6 (4 + 2) y el quinto elemento a 6 (3 + 3).
Entonces, el costo total es 2 + 2 + 3 = 7Entrada: arr[] = {3, 3, 3, 3}
Salida: 10
Enfoque: La idea es agregar la menor cantidad posible de números primos a los elementos del arreglo para que el arreglo no sea decreciente. A continuación se muestran los pasos:
- Inicialice una variable para almacenar el costo mínimo, digamos res .
- Genere y almacene todos los números primos hasta el 10 7 usando el tamiz de Eratóstenes .
- Ahora, recorra la array y realice los siguientes pasos:
- Si el elemento actual es menor que el elemento anterior, encuentre el número primo más pequeño (por ejemplo, el primo_más cercano ) que se puede agregar para que la array no disminuya.
- Actualice el elemento actual arr[i] = arr[i] + close_prime .
- Agregue más cercano_primo a res .
- Imprime el valor final de res obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define MAX 10000000 // Stores if an index is a // prime / non-prime value bool isPrime[MAX]; // Stores the prime vector<int> primes; // Function to generate all // prime numbers void SieveOfEratosthenes() { memset(isPrime, true, sizeof(isPrime)); for (int p = 2; p * p <= MAX; p++) { // If current element is prime if (isPrime[p] == true) { // Set all its multiples non-prime for (int i = p * p; i <= MAX; i += p) isPrime[i] = false; } } // Store all prime numbers for (int p = 2; p <= MAX; p++) if (isPrime[p]) primes.push_back(p); } // Function to find the closest // prime to a particular number int prime_search(vector<int> primes, int diff) { // Applying binary search // on primes vector int low = 0; int high = primes.size() - 1; int res; while (low <= high) { int mid = (low + high) / 2; // If the prime added makes // the elements equal if (primes[mid] == diff) { // Return this as the // closest prime return primes[mid]; } // If the array remains // non-decreasing else if (primes[mid] < diff) { // Search for a bigger // prime number low = mid + 1; } // Otherwise else { res = primes[mid]; // Check if a smaller prime can // make array non-decreasing or not high = mid - 1; } } // Return closest number return res; } // Function to find the minimum cost int minCost(int arr[], int n) { // Find all primes SieveOfEratosthenes(); // Store the result int res = 0; // Iterate over the array for (int i = 1; i < n; i++) { // Current element is less // than the previous element if (arr[i] < arr[i - 1]) { int diff = arr[i - 1] - arr[i]; // Find the closest prime which // makes the array non decreasing int closest_prime = prime_search(primes, diff); // Add to overall cost res += closest_prime; // Update current element arr[i] += closest_prime; } } // Return the minimum cost return res; } // Driver Code int main() { // Given array int arr[] = { 2, 1, 5, 4, 3 }; int n = 5; // Function Call cout << minCost(arr, n); return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ static final int MAX = 10000000; // Stores if an index is a // prime / non-prime value static boolean []isPrime = new boolean[MAX + 1]; // Stores the prime static Vector<Integer> primes = new Vector<Integer>(); // Function to generate all // prime numbers static void SieveOfEratosthenes() { Arrays.fill(isPrime, true); for(int p = 2; p * p <= MAX; p++) { // If current element is prime if (isPrime[p] == true) { // Set all its multiples non-prime for(int i = p * p; i <= MAX; i += p) isPrime[i] = false; } } // Store all prime numbers for(int p = 2; p <= MAX; p++) if (isPrime[p]) primes.add(p); } // Function to find the closest // prime to a particular number static int prime_search(Vector<Integer> primes, int diff) { // Applying binary search // on primes vector int low = 0; int high = primes.size() - 1; int res = -1; while (low <= high) { int mid = (low + high) / 2; // If the prime added makes // the elements equal if (primes.get(mid) == diff) { // Return this as the // closest prime return primes.get(mid); } // If the array remains // non-decreasing else if (primes.get(mid) < diff) { // Search for a bigger // prime number low = mid + 1; } // Otherwise else { res = primes.get(mid); // Check if a smaller prime can // make array non-decreasing or not high = mid - 1; } } // Return closest number return res; } // Function to find the minimum cost static int minCost(int arr[], int n) { // Find all primes SieveOfEratosthenes(); // Store the result int res = 0; // Iterate over the array for(int i = 1; i < n; i++) { // Current element is less // than the previous element if (arr[i] < arr[i - 1]) { int diff = arr[i - 1] - arr[i]; // Find the closest prime which // makes the array non decreasing int closest_prime = prime_search(primes, diff); // Add to overall cost res += closest_prime; // Update current element arr[i] += closest_prime; } } // Return the minimum cost return res; } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 2, 1, 5, 4, 3 }; int n = 5; // Function call System.out.print(minCost(arr, n)); } } // This code is contributed by Amit Katiyar
Python3
# Python3 Program to implement # the above approach MAX = 10000000 # Stores if an index is a # prime / non-prime value isPrime = [True] * (MAX + 1) # Stores the prime primes = [] # Function to generate all # prime numbers def SieveOfEratosthenes(): global isPrime p = 2 while p * p <= MAX: # If current element is prime if (isPrime[p] == True): # Set all its multiples non-prime for i in range (p * p, MAX + 1, p): isPrime[i] = False p += 1 # Store all prime numbers for p in range (2, MAX + 1): if (isPrime[p]): primes.append(p) # Function to find the closest # prime to a particular number def prime_search(primes, diff): # Applying binary search # on primes vector low = 0 high = len(primes) - 1 while (low <= high): mid = (low + high) // 2 # If the prime added makes # the elements equal if (primes[mid] == diff): # Return this as the # closest prime return primes[mid] # If the array remains # non-decreasing elif (primes[mid] < diff): # Search for a bigger # prime number low = mid + 1 # Otherwise else: res = primes[mid] # Check if a smaller prime can # make array non-decreasing or not high = mid - 1 # Return closest number return res # Function to find the minimum cost def minCost(arr, n): # Find all primes SieveOfEratosthenes() # Store the result res = 0 # Iterate over the array for i in range (1, n): # Current element is less # than the previous element if (arr[i] < arr[i - 1]): diff = arr[i - 1] - arr[i] # Find the closest prime which # makes the array non decreasing closest_prime = prime_search(primes, diff) # Add to overall cost res += closest_prime # Update current element arr[i] += closest_prime # Return the minimum cost return res # Driver Code if __name__ == "__main__": # Given array arr = [2, 1, 5, 4, 3] n = 5 #Function Call print (minCost(arr, n)) # This code is contributed by Chitranayal
C#
// C# program to implement // the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ static int MAX = 10000000; // Stores if an index is a // prime / non-prime value static bool []isPrime = new bool[MAX + 1]; // Stores the prime static ArrayList primes = new ArrayList(); // Function to generate all // prime numbers static void SieveOfEratosthenes() { Array.Fill(isPrime, true); for(int p = 2; p * p <= MAX; p++) { // If current element is prime if (isPrime[p] == true) { // Set all its multiples non-prime for(int i = p * p; i <= MAX; i += p) isPrime[i] = false; } } // Store all prime numbers for(int p = 2; p <= MAX; p++) if (isPrime[p]) primes.Add(p); } // Function to find the closest // prime to a particular number static int prime_search(ArrayList primes, int diff) { // Applying binary search // on primes vector int low = 0; int high = primes.Count - 1; int res = -1; while (low <= high) { int mid = (low + high) / 2; // If the prime added makes // the elements equal if ((int)primes[mid] == diff) { // Return this as the // closest prime return (int)primes[mid]; } // If the array remains // non-decreasing else if ((int)primes[mid] < diff) { // Search for a bigger // prime number low = mid + 1; } // Otherwise else { res = (int)primes[mid]; // Check if a smaller prime can // make array non-decreasing or not high = mid - 1; } } // Return closest number return res; } // Function to find the minimum cost static int minCost(int []arr, int n) { // Find all primes SieveOfEratosthenes(); // Store the result int res = 0; // Iterate over the array for(int i = 1; i < n; i++) { // Current element is less // than the previous element if (arr[i] < arr[i - 1]) { int diff = arr[i - 1] - arr[i]; // Find the closest prime which // makes the array non decreasing int closest_prime = prime_search(primes, diff); // Add to overall cost res += closest_prime; // Update current element arr[i] += closest_prime; } } // Return the minimum cost return res; } // Driver Code public static void Main(string[] args) { // Given array int []arr = { 2, 1, 5, 4, 3 }; int n = 5; // Function call Console.Write(minCost(arr, n)); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript Program to implement // the above approach let MAX = 10000000; // Stores if an index is a // prime / non-prime value let isPrime = new Array(MAX); // Stores the prime let primes = new Array(); // Function to generate all // prime numbers function SieveOfEratosthenes() { isPrime.fill(true); for (let p = 2; p * p <= MAX; p++) { // If current element is prime if (isPrime[p] == true) { // Set all its multiples non-prime for (let i = p * p; i <= MAX; i += p) isPrime[i] = false; } } // Store all prime numbers for (let p = 2; p <= MAX; p++) if (isPrime[p]) primes.push(p); } // Function to find the closest // prime to a particular number function prime_search(primes, diff) { // Applying binary search // on primes vector let low = 0; let high = primes.length - 1; let res = 0; while (low <= high) { let mid = Math.floor((low + high) / 2); // If the prime added makes // the elements equal if (primes[mid] == diff) { // Return this as the // closest prime return primes[mid]; } // If the array remains // non-decreasing else if (primes[mid] < diff) { // Search for a bigger // prime number low = mid + 1; } // Otherwise else { res = primes[mid]; // Check if a smaller prime can // make array non-decreasing or not high = mid - 1; } } // Return closest number return res; } // Function to find the minimum cost function minCost(arr, n) { // Find all primes SieveOfEratosthenes(); // Store the result let res = 0; // Iterate over the array for (let i = 1; i < n; i++) { // Current element is less // than the previous element if (arr[i] < arr[i - 1]) { let diff = arr[i - 1] - arr[i]; // Find the closest prime which // makes the array non decreasing let closest_prime = prime_search(primes, diff); // Add to overall cost res += closest_prime; // Update current element arr[i] += closest_prime; } } // Return the minimum cost return res; } // Driver Code // Given array let arr = [ 2, 1, 5, 4, 3 ]; let n = 5; // Function Call document.write(minCost(arr, n)) // This code is contributed by gfgking </script>
7
Complejidad de tiempo: O(N*log(logN))
Espacio auxiliar: O(N)