Maximice el tamaño de la array eliminando exactamente k sub-arrays para convertir la array en prima

Dada una array arr[] de N enteros positivos y un entero no negativo K . La tarea es eliminar exactamente K subarreglos de la array de modo que todos los elementos restantes de la array sean primos y el tamaño de la array restante sea el máximo posible.

Ejemplos: 

Entrada: arr[] = {2, 4, 2, 2, 4, 2, 4, 2}, k = 2 
Salida: 4 
Elimine los subarreglos arr[1] y arr[4…6] y 
el arreglo principal restante se ser {2, 2, 2, 2}

Entrada: arr[] = {2, 4, 2, 2, 4, 2, 4, 2}, k = 3 
Salida: 5 

Un enfoque simple sería buscar todos los subconjuntos que nos costarían una complejidad de tiempo O(N ² ) y luego realizar un seguimiento del número de números primos o compuestos en una longitud particular de subconjunto.

Un enfoque eficiente es realizar un seguimiento del número de números primos entre dos compuestos consecutivos.

1. Paso de preprocesamiento: almacene todos los números primos en la array de números primos utilizando Tamiz de Eratóstenes
2. Calcule los índices de todos los números compuestos en un vector v.
3. Calcule la distancia entre dos índices consecutivos del vector descrito anteriormente en un vector diff ya que esto almacenará el número de números primos entre dos compuestos consecutivos cualesquiera.
4. Ordenar este vector. Después de ordenar, obtenemos el subarreglo que contiene el menor número de números primos hasta el número más alto de números primos.
5. Calcule la suma del prefijo de este vector. Ahora, cada índice de diff denota el valor k y el valor en diff denota el número de números primos que se eliminarán al eliminar k subarreglos. El índice 0 denota el k más grande menor que el tamaño de v, el índice 1 denota el k más grande en segundo lugar, y así sucesivamente. Entonces, del vector de suma de prefijos, obtenemos directamente el número de números primos que se eliminarán.

Después de realizar los pasos anteriores, nuestra solución depende de tres casos: 

1. Este es un caso imposible si k es 0 y hay enteros compuestos en la array.
2. Si k es mayor o igual que ninguno de los compuestos, entonces podemos eliminar todos los números enteros compuestos y los números primos adicionales para igualar el valor de k. Todos estos subarreglos son de tamaño 1, lo que nos da las respuestas óptimas.
3. Si k es menor que no de los números enteros compuestos, entonces tenemos que eliminar los subarreglos que contienen todos los compuestos y ninguno de los números primos que caen en esos subarreglos.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;
bool prime[N];
 
// Sieve of Eratosthenes
void sieve()
{
    for (int i = 2; i < N; i++) {
        if (!prime[i]) {
            for (int j = i + i; j < N; j += i) {
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}
 
// Function to return the size
// of the maximized array
int maxSizeArr(int* arr, int n, int k)
{
    vector<int> v, diff;
 
    // Insert the indices of composite numbers
    for (int i = 0; i < n; i++) {
        if (prime[arr[i]])
            v.push_back(i);
    }
 
    // Compute the number of prime between
    // two consecutive composite
    for (int i = 1; i < v.size(); i++) {
        diff.push_back(v[i] - v[i - 1] - 1);
    }
 
    // Sort the diff vector
    sort(diff.begin(), diff.end());
 
    // Compute the prefix sum of diff vector
    for (int i = 1; i < diff.size(); i++) {
        diff[i] += diff[i - 1];
    }
 
    // Impossible case
    if (k > n || (k == 0 && v.size())) {
        return -1;
    }
 
    // Delete sub-arrays of length 1
    else if (v.size() <= k) {
        return (n - k);
    }
 
    // Find the number of primes to be deleted
    // when deleting the sub-arrays
    else if (v.size() > k) {
        int tt = v.size() - k;
        int sum = 0;
        sum += diff[tt - 1];
        int res = n - (v.size() + sum);
        return res;
    }
}
 
// Driver code
int main()
{
    sieve();
    int arr[] = { 2, 4, 2, 2, 4, 2, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxSizeArr(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
static int N = 10000005;
static int []prime = new int[N];
 
// Sieve of Eratosthenes
static void sieve()
{
    for (int i = 2; i < N; i++)
    {
        if (prime[i] == 0)
        {
            for (int j = i + i; j < N; j += i)
            {
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}
 
// Function to return the size
// of the maximized array
static int maxSizeArr(int arr[], int n, int k)
{
    ArrayList<Integer> v = new ArrayList<Integer>();
    ArrayList<Integer> diff = new ArrayList<Integer>();
 
    // Insert the indices of composite numbers
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        if (prime[arr[i]] == 1)
        {
            v.add(i);
        }
    }
 
    // Compute the number of prime between
    // two consecutive composite
    num = 0;
    for (int i = 1; i < v.size(); i++)
    {
        diff.add(v.get(i) - v.get(i - 1) - 1);
    }
 
    // Sort the diff vector
    Collections.sort(diff);
 
    // Compute the prefix sum of diff vector
    for (int i = 1; i < diff.size(); i++)
    {
        diff.set(i, diff.get(i) + diff.get(i - 1));
    }
 
    // Impossible case
    if (k > n || (k == 0 && v.size() > 0))
    {
        return -1;
    }
 
    // Delete sub-arrays of length 1
    else if (v.size() <= k)
    {
        return (n - k);
    }
 
    // Find the number of primes to be deleted
    // when deleting the sub-arrays
    else if (v.size() > k)
    {
        int tt = v.size() - k;
        int sum = 0;
        sum += diff.get(tt - 1);
        int res = n - (v.size() + sum);
        return res;
    }
    return 1;
}
     
// Driver code
public static void main(String []args)
{
    sieve();
    int []arr = { 2, 4, 2, 2, 4, 2, 4, 2 };
    int n = arr.length;
    int k = 2;
    System.out.println(maxSizeArr(arr, n, k));
}
}
 
// This code is contributed by Surendra_Gangwar

# Python implementation of above approach
 
N = 10000005
prime = [False]*N
 
# Sieve of Eratosthenes
def sieve():
    for i in range(2,N):
        if not prime[i]:
            for j in range(i+1,N):
                prime[j] = True
     
    prime[1] = True
 
# Function to return the size
# of the maximized array
def maxSizeArr(arr, n, k):
    v, diff = [], []
 
    # Insert the indices of composite numbers
    for i in range(n):
        if prime[arr[i]]:
            v.append(i)
     
    # Compute the number of prime between
    # two consecutive composite
    for i in range(1, len(v)):
        diff.append(v[i] - v[i-1] -1)
     
    # Sort the diff vector
    diff.sort()
 
    # Compute the prefix sum of diff vector
    for i in range(1, len(diff)):
        diff[i] += diff[i-1]
     
    # Impossible case
    if k > n or (k == 0 and len(v)):
        return -1
     
    # Delete sub-arrays of length 1
    elif len(v) <= k:
        return (n-k)
     
    # Find the number of primes to be deleted
    # when deleting the sub-arrays
    elif len(v) > k:
        tt = len(v) - k
        s = 0
        s += diff[tt-1]
        res = n - (len(v) + s)
        return res
 
 
# Driver code
if __name__ == "__main__":
     
    sieve()
 
    arr = [2, 4, 2, 2, 4, 2, 4, 2]
    n = len(arr)
    k = 2
 
    print(maxSizeArr(arr, n, k))
 
# This code is contributed by
# sanjeev2552

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static int N = 1000005;
static int []prime = new int[N];
 
// Sieve of Eratosthenes
static void sieve()
{
    for(int i = 2; i < N; i++)
    {
        if (prime[i] == 0)
        {
            for(int j = i + i;
                    j < N; j += i)
            {
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}
 
// Function to return the size
// of the maximized array
static int maxSizeArr(int []arr, int n,
                                 int k)
{
    List<int> v = new List<int>();
    List<int> diff = new List<int>();
 
    // Insert the indices of composite numbers
    //int num = 0;
     
    for(int i = 0; i < n; i++)
    {
        if (prime[arr[i]] == 1)
        {
            v.Add(i);
        }
    }
 
    // Compute the number of prime between
    // two consecutive composite
    //num = 0;
    for(int i = 1; i < v.Count; i++)
    {
        diff.Add(v[i] - v[i - 1] - 1);
    }
 
    // Sort the diff vector
    diff.Sort();
 
    // Compute the prefix sum of diff vector
    for(int i = 1; i < diff.Count; i++)
    {
        diff[i] = diff[i] + diff[i - 1];
    }
 
    // Impossible case
    if (k > n || (k == 0 && v.Count > 0))
    {
        return -1;
    }
 
    // Delete sub-arrays of length 1
    else if (v.Count <= k)
    {
        return (n - k);
    }
 
    // Find the number of primes to be deleted
    // when deleting the sub-arrays
    else if (v.Count > k)
    {
        int tt = v.Count - k;
        int sum = 0;
        sum += diff[tt - 1];
        int res = n - (v.Count + sum);
        return res;
    }
    return 1;
}
     
// Driver code
public static void Main(String []args)
{
    sieve();
    int []arr = { 2, 4, 2, 2, 4, 2, 4, 2 };
    int n = arr.Length;
    int k = 2;
     
    Console.WriteLine(maxSizeArr(arr, n, k));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript implementation of the approach
 
 
const N = 1e7 + 5;
let prime = new Array(N);
 
// Sieve of Eratosthenes
function sieve() {
    for (let i = 2; i < N; i++) {
        if (!prime[i]) {
            for (let j = i + i; j < N; j += i) {
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}
 
// Function to return the size
// of the maximized array
function maxSizeArr(arr, n, k) {
    let v = new Array();
    let diff = new Array();
 
    // Insert the indices of composite numbers
    for (let i = 0; i < n; i++) {
        if (prime[arr[i]])
            v.push(i);
    }
 
    // Compute the number of prime between
    // two consecutive composite
    for (let i = 1; i < v.length; i++) {
        diff.push(v[i] - v[i - 1] - 1);
    }
 
    // Sort the diff vector
    diff.sort((a, b) => a - b);
 
    // Compute the prefix sum of diff vector
    for (let i = 1; i < diff.length; i++) {
        diff[i] += diff[i - 1];
    }
 
    // Impossible case
    if (k > n || (k == 0 && v.length)) {
        return -1;
    }
 
    // Delete sub-arrays of length 1
    else if (v.length <= k) {
        return (n - k);
    }
 
    // Find the number of primes to be deleted
    // when deleting the sub-arrays
    else if (v.length > k) {
        let tt = v.length - k;
        let sum = 0;
        sum += diff[tt - 1];
        let res = n - (v.length + sum);
        return res;
    }
}
 
// Driver code
 
sieve();
let arr = [2, 4, 2, 2, 4, 2, 4, 2];
let n = arr.length;
let k = 2;
document.write(maxSizeArr(arr, n, k));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

4

Complejidad de tiempo: O(N*logN), ya que estamos usando una función de ordenación incorporada para ordenar una array de tamaño N. Donde N es el número de elementos en la array.

Espacio auxiliar: O (10000005), ya que usamos espacio adicional para la array principal.