Cambios mínimos requeridos para hacer que todos los elementos de Array sean Prime

Dada una array de enteros arr[] , la tarea es contar el número mínimo de cambios necesarios para convertir cada elemento de la array a su número primo más cercano.
Ejemplos: 

Entrada: arr[] = {4, 25, 13, 6, 20} 
Salida:
Explicación: 

  • Se requiere 1 incremento para convertir 4 a su 5 primo más cercano.
  • Se requieren 2 decrementos para convertir 25 a su primo 23 más cercano.
  • 13 en sí mismo es un número primo.
  • Se requiere 1 incremento para convertir 6 a su 7 primo más cercano.
  • Se requiere 1 decremento para convertir 20 a su primo 19 más cercano.

Por lo tanto, número requerido de cambios = 1 + 2 + 0 + 1 + 1 = 5

Entrada: arr[] = {1, 2, 9} 
Salida:
Explicación: 

  • Se requiere 1 incremento para convertir 1 a su primo 2 más cercano.
  • 2 en sí mismo es un número primo.
  • Se requieren 2 incrementos para convertir 9 a su 11 primo más cercano.

Por lo tanto, número requerido de cambios = 1 + 0 + 2 = 3 

Enfoque ingenuo: 
recorra la array y, para cada elemento de la array, encuentre su número primo más cercano a su derecha comenzando desde arr[i] + 1 y a su izquierda comenzando desde arr[i] – 1. Una vez calculado, calcule su diferencia desde arr[ i] y considere la diferencia más pequeña. La suma de todas esas diferencias da el resultado deseado. 

Complejidad de tiempo: O(N * maxi 2 ), donde maxi denota el elemento máximo en la array.

Enfoque eficiente: 
este problema se puede resolver utilizando la criba de Eratóstenes . Siga los pasos a continuación para resolver el problema: 

  • Encuentre el elemento máximo de la array dada.
  • Sea maxi el elemento máximo presente en la array. Genere todos los números primos en el rango [1, 2*maxi] y guárdelos.
  • Recorra la array y encuentre el índice del siguiente número primo mayor para cada elemento de la array usando lower_bound , digamos x .
  • Calcula la diferencia absoluta entre arr[i] y primos[x] y entre arr[i] y primos[x – 1].
  • Sume el mínimo de los dos a ans .
  • Después de completar el recorrido de la array, imprima el valor final de ans como respuesta.

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;
 
// Function to generate all primes
vector<int> SieveOfEratosthenes(int n)
{
    bool prime[2 * n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= 2 * n; p++) {
 
        // If p is a prime
        if (prime[p] == true) {
 
            // Mark all its multiples
            // as non-prime
            for (int i = p * p; i <= 2 * n;
                 i += p)
                prime[i] = false;
        }
    }
 
    vector<int> primes;
 
    // Store all prime numbers
    for (int p = 2; p <= 2 * n; p++)
        if (prime[p])
            primes.push_back(p);
 
    // Return the list of primes
    return primes;
}
 
// Function to calculate the
// minimum increments to
// convert every array elements
// to a prime
int minChanges(vector<int> arr)
{
    int n = arr.size();
    int ans = 0;
 
    // Extract maximum element
    // of the given array
    int maxi = *max_element(arr.begin(),
                            arr.end());
 
    vector<int> primes
        = SieveOfEratosthenes(maxi);
 
    for (int i = 0; i < n; i++) {
 
        // Extract the index which has
        // the next greater prime
        int x = lower_bound(primes.begin(),
                            primes.end(),
                            arr[i])
                - primes.begin();
 
        // Store the difference
        // between the prime and
        // the array element
        int minm = abs(primes[x]
                       - arr[i]);
 
        if (x > 1) {
            minm = min(minm,
                       abs(primes[x - 1]
                           - arr[i]));
        }
 
        ans += minm;
    }
    return ans;
}
 
// Driver Code
int main()
{
 
    vector<int> arr
        = { 4, 25, 13, 6, 20 };
 
    cout << minChanges(arr);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
 
// Function to generate all primes
static ArrayList<Integer> SieveOfEratosthenes(int n)
{
    boolean[] prime = new boolean[2 * n + 1];
    Arrays.fill(prime, true);
 
    for(int p = 2; p * p <= 2 * n; p++)
    {
         
        // If p is a prime
        if (prime[p] == true)
        {
             
            // Mark all its multiples
            // as non-prime
            for(int i = p * p;
                    i <= 2 * n; i += p)
                prime[i] = false;
        }
    }
     
    ArrayList<Integer> primes = new ArrayList<>();
 
    // Store all prime numbers
    for(int p = 2; p <= 2 * n; p++)
        if (prime[p])
            primes.add(p);
 
    // Return the list of primes
    return primes;
}
 
// Function to calculate the
// minimum increments to
// convert every array elements
// to a prime
static int minChanges(int[] arr)
{
    int n = arr.length;
    int ans = 0;
 
    // Extract maximum element
    // of the given array
    int maxi = arr[0];
    for(int i = 1; i < arr.length; i++)
        maxi = Math.max(maxi, arr[i]);
         
    ArrayList<Integer> primes = SieveOfEratosthenes(maxi);
 
    for(int i = 0; i < n; i++)
    {
         
        // Extract the index which has
        // the next greater prime
        int x = -1;
        for(int j = 0; j < primes.size(); j++)
        {
            if (arr[i] == primes.get(j))
            {
                x = j;
                break;
            }
            else if (arr[i] < primes.get(j))
            {
                x = j;
                break;
            }
        }
         
        // Store the difference
        // between the prime and
        // the array element
        int minm = Math.abs(primes.get(x) - arr[i]);
     
        if (x > 1)
        {
            minm = Math.min(minm,
                            Math.abs(primes.get(x - 1) -
                                     arr[i]));
        }
        ans += minm;
    }
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
    int[] arr = { 4, 25, 13, 6, 20 };
     
    System.out.println(minChanges(arr));
}
}
 
// This code is contributed by offbeat

Python3

# Python program to implement
# the above approach
 
# Function to generate all primes
def SieveOfEratosthenes(n):
    prime = [True for i in range(2 * n + 1)]
    p = 2
    while(p * p <= 2 * n):
       
        # If p is a prime
        if(prime[p] == True):
             
            # Mark all its multiples
            # as non-prime
            i = p * p
            while(i <= n * 2):
                prime[i] = False
                i += p
        p += 1
    primes = []
     
    # Store all prime numbers
    for p in range(2, (2 * n) + 1):
        if(prime[p]):
            primes.append(p)
 
    # Return the list of primes
    return primes
 
# Function to calculate the
# minimum increments to
# convert every array elements
# to a prime
def minChanges(arr):
    n = len(arr)
    ans = 0
     
    # Extract maximum element
    # of the given array
    maxi = max(arr)
    primes = SieveOfEratosthenes(maxi)
    for i in range(n):
       
        # Extract the index which has
        # the next greater prime
        x = -1
        for j in range(len(primes)):
            if(arr[i] == primes[j]):
                x = j
                break
            elif(arr[i] < primes[j]):
                x = j
                break
                 
        # Store the difference
        # between the prime and
        # the array element
        minm = abs(primes[x] - arr[i])
 
        if(x > 1):
            minm = min(minm, abs(primes[x - 1]-arr[i]))
        ans += minm
    return ans
 
# Driver code
arr = [4, 25, 13, 6, 20]
print(minChanges(arr))
 
# This code is contributed by avanitrachhadiya2155

C#

// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
 
// Function to generate all primes
static List<int> SieveOfEratosthenes(int n)
{
    bool[] prime = new bool[2 * n + 1];
    Array.Fill(prime, true);
 
    for(int p = 2; p * p <= 2 * n; p++)
    {
         
        // If p is a prime
        if (prime[p] == true)
        {
             
            // Mark all its multiples
            // as non-prime
            for(int i = p * p; i <= 2 * n; i += p)
                prime[i] = false;
        }
    }  
    List<int> primes = new List<int>();
 
    // Store all prime numbers
    for(int p = 2; p <= 2 * n; p++)
        if (prime[p])
            primes.Add(p);
 
    // Return the list of primes
    return primes;
}
 
// Function to calculate the
// minimum increments to
// convert every array elements
// to a prime
static int minChanges(int[] arr)
{
    int n = arr.Length;
    int ans = 0;
 
    // Extract maximum element
    // of the given array
    int maxi = arr[0];
    for(int i = 1; i < arr.Length; i++)
        maxi = Math.Max(maxi, arr[i]);       
    List<int> primes = SieveOfEratosthenes(maxi);
    for(int i = 0; i < n; i++)
    {
         
        // Extract the index which has
        // the next greater prime
        int x = -1;
        for(int j = 0; j < primes.Count; j++)
        {
            if (arr[i] == primes[j])
            {
                x = j;
                break;
            }
            else if (arr[i] < primes[j])
            {
                x = j;
                break;
            }
        }
         
        // Store the difference
        // between the prime and
        // the array element
        int minm = Math.Abs(primes[x]- arr[i]);
     
        if (x > 1)
        {
            minm = Math.Min(minm,
                            Math.Abs(primes[x - 1] -
                                     arr[i]));
        }
        ans += minm;
    }
    return ans;
}
 
// Driver code
public static void Main(string[] args)
{
    int[] arr = { 4, 25, 13, 6, 20 };
     
    Console.Write(minChanges(arr));
}
}
 
// This code is contributed by rutvik_56.

Javascript

<script>
// Javascript Program to implement
// the above approach
 
 
// Function to generate all primes
function SieveOfEratosthenes(n)
{
    let prime  = new Array(2 * n + 1);
    prime.fill(true)
 
    for (let p = 2; p * p <= 2 * n; p++) {
 
        // If p is a prime
        if (prime[p] == true) {
 
            // Mark all its multiples
            // as non-prime
            for (let i = p * p; i <= 2 * n;
                i += p)
                prime[i] = false;
        }
    }
 
    let primes = new Array();
 
    // Store all prime numbers
    for (let p = 2; p <= 2 * n; p++)
        if (prime[p])
            primes.push(p);
 
    // Return the list of primes
    return primes;
}
 
// Function to calculate the
// minimum increments to
// convert every array elements
// to a prime
function minChanges(arr)
{
    let n = arr.length;
    let ans = 0;
 
    // Extract maximum element
    // of the given array
    let maxi = arr.sort((a, b) => b - a)[0];
 
    let primes
        = SieveOfEratosthenes(maxi);
 
    for (let i = 0; i < n; i++) {
 
        // Extract the index which has
        // the next greater prime
         
        let x = -1
        for(let j = 0; j < primes.length; j++){
            if(arr[i] == primes[j]){
                x = j
                break
            }
            else if(arr[i] < primes[j]){
                x = j
                break
            }
        }
        // Store the difference
        // between the prime and
        // the array element
        let minm = Math.abs(primes[x]
                    - arr[i]);
 
        if (x > 1) {
            minm = Math.min(minm,
                    Math.abs(primes[x - 1]
                        - arr[i]));
        }
 
        ans += minm;
    }
    return ans;
}
 
// Driver Code
 
 
    let arr = [ 4, 25, 13, 6, 20 ];
 
    document.write(minChanges(arr));
 
// This code is contributed by _saurabh_jaiswal
</script>
Producción: 

5

 

Complejidad de tiempo: O(log(log(N)) + O(NlogN) 
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por Thirumalaisrinivasan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *