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>
Producción:
7
Complejidad de tiempo: O(N*log(logN))
Espacio auxiliar: O(N)