Modifique la array fusionando elementos con suma de modo que consista solo en números primos.

Dada una array arr[] que consta de enteros positivos, la tarea es verificar si podemos modificar la array agregando cualquiera de los elementos de la array de modo que consista solo en números primos .

Ejemplos:

Entrada: arr[] = {3, 5, 7, 21} 
Salida: SÍ 
Explicación: 
Agregue los siguientes elementos, 3+5+21 
Entonces la array se convierte en {7, 29} que consiste solo en números primos.

Entrada: {2, 5, 12, 16} 
Salida: NO 
Explicación: 
No hay combinación posible entre los elementos que hagan que el arreglo contenga todos los números primos

Entrada: {3, 5, 13, 22} 
Salida: SÍ 
Explicación: 
Solo es posible una combinación, 
suma todos los elementos: 3+5+13+22 = {43} que es solo primo

Prerrequisitos : Enfoque Bitmasking-DP
:

• Podemos resolver este problema usando Programación Dinámica con Máscaras de Bits . Podemos representar nuestro estado DP como una máscara que es un subconjunto de elementos.
• Entonces, dejemos que nuestra array dp sea DP [máscara], que representa si hasta esta máscara (los elementos elegidos) el subconjunto formado será solo primos .
• El número máximo de bits en la máscara será el número de elementos en la array.
• Seguimos marcando los elementos codificados como una secuencia en la máscara (si se selecciona el i-ésimo elemento de índice, entonces el i-ésimo bit se establece en la máscara) y seguimos comprobando si el elemento elegido actual (suma actual) es primo, si es es primo y se visitan todos los demás elementos, luego devolvemos true y obtenemos la respuesta.
• De lo contrario, si no se visitan otros elementos, entonces como la suma actual es primo, solo necesitamos buscar otros elementos que puedan individualmente o sumando para formar algunos números primos, para que podamos marcar nuestra suma actual como 0 nuevamente.
• Si la máscara está llena (se visitan todos los elementos) y la suma actual no es primo, devolvemos falso , porque hay al menos una suma que no es primo.
• Recurrencia :

DP[mask] = solve(curr + arr[i], mask | 1<<i)     
where 0 <= i < n

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

// C++ program to find the
// array of primes
#include <bits/stdc++.h>
using namespace std;
 
// DP array to store the
// ans for max 20 elements
bool dp[1 << 20];
 
// To check whether the
// number is prime or not
bool isprime(int n)
{
    if (n == 1)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
 
// Function to check whether the
// array can be modify so that
// there are only primes
int solve(int arr[], int curr,
          int mask, int n)
{
 
    // If curr is prime and all
    // elements are visited,
    // return true
    if (isprime(curr))
    {
        if (mask == (1 << n) - 1)
        {
            return true;
        }
 
        // If all elements are not
        // visited, set curr=0, to
        // search for new prime sum
        curr = 0;
    }
 
    // If all elements are visited
    if (mask == (1 << n) - 1)
    {
 
        // If the current sum is
        // not prime return false
        if (!isprime(curr))
        {
            return false;
        }
    }
 
    // If this state is already
    // calculated, return the
    // answer directly
    if (dp[mask])
        return dp[mask];
 
    // Try all state of mask
    for (int i = 0; i < n; i++)
    {
        // If ith index is not set
        if (!(mask & 1 << i))
        {
            // Add the current element
            // and set ith index and recur
            if (solve(arr, curr + arr[i]
                      , mask | 1 << i, n))
            {
                // If subset can be formed
                // then return true
                return true;
            }
        }
    }
     
    // After every possibility of mask,
    // if the subset is not formed,
    // return false by memoizing.
    return dp[mask] = false;
}
 
// Driver code
int main()
{
 
    int arr[] = { 3, 6, 7, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
     
    if(solve(arr, 0, 0, n))
    {
        cout << "YES";
    }
    else
    {
         cout << "NO";
    }
    return 0;
    
}

// Java program to find the array of primes
import java.util.*;
 
class GFG{
 
// dp array to store the
// ans for max 20 elements
static boolean []dp = new boolean[1 << 20];
 
// To check whether the
// number is prime or not
static boolean isprime(int n)
{
    if (n == 1)
        return false;
 
    for(int i = 2; i * i <= n; i++)
    {
       if (n % i == 0)
       {
           return false;
       }
    }
    return true;
}
 
// Function to check whether the
// array can be modify so that
// there are only primes
static boolean solve(int arr[], int curr,
                     int mask, int n)
{
 
    // If curr is prime and all
    // elements are visited,
    // return true
    if (isprime(curr))
    {
        if (mask == (1 << n) - 1)
        {
            return true;
        }
 
        // If all elements are not
        // visited, set curr=0, to
        // search for new prime sum
        curr = 0;
    }
 
    // If all elements are visited
    if (mask == (1 << n) - 1)
    {
 
        // If the current sum is
        // not prime return false
        if (!isprime(curr))
        {
            return false;
        }
    }
 
    // If this state is already
    // calculated, return the
    // answer directly
    if (dp[mask])
        return dp[mask];
 
    // Try all state of mask
    for(int i = 0; i < n; i++)
    {
        
       // If ith index is not set
       if ((mask & (1 << i)) == 0)
       {
            
           // Add the current element
           // and set ith index and recur
           if (solve(arr, curr + arr[i],
                     mask | 1 << i, n))
           {
                
               // If subset can be formed
               // then return true
               return true;
           }
       }
    }
     
    // After every possibility of mask,
    // if the subset is not formed,
    // return false by memoizing.
    return dp[mask] = false;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 6, 7, 13 };
    int n = arr.length;
     
    if(solve(arr, 0, 0, n))
    {
        System.out.print("YES");
    }
    else
    {
        System.out.print("NO");
    }
}
}
 
// This code is contributed by Rohit_ranjan

# Python3 program to find the array
# of primes
 
# DP array to store the
# ans for max 20 elements
dp = [0] * (1 << 20)
 
# To check whether the
# number is prime or not
def isprime(n):
     
    if (n == 1):
        return False
    for i in range(2, n + 1):
        if (n % i == 0):
            return False
     
    return True
 
# Function to check whether the
# array can be modify so that
# there are only primes
def solve(arr, curr, mask, n):
 
    # If curr is prime and all
    # elements are visited,
    # return true
    if (isprime(curr)):
        if (mask == (1 << n) - 1):
            return True
         
        # If all elements are not
        # visited, set curr=0, to
        # search for new prime sum
        curr = 0
     
    # If all elements are visited
    if (mask == (1 << n) - 1):
 
        # If the current sum is
        # not prime return false
        if (isprime(curr) == False):
            return False
         
    # If this state is already
    # calculated, return the
    # answer directly
    if (dp[mask] != False):
        return dp[mask]
 
    # Try all state of mask
    for i in range(n):
         
        # If ith index is not set
        if ((mask & 1 << i) == False):
             
            # Add the current element
            # and set ith index and recur
            if (solve(arr, curr + arr[i],
                           mask | 1 << i, n)):
                                
                # If subset can be formed
                # then return true
                return True
                 
    # After every possibility of mask,
    # if the subset is not formed,
    # return false by memoizing.
    return (dp[mask] == False)
 
# Driver code
arr = [ 3, 6, 7, 13 ]
 
n = len(arr)
     
if (solve(arr, 0, 0, n)):
    print("YES")
else:
    print("NO")
     
# This code is contributed by code_hunt

// C# program to find the array of primes
using System;
 
class GFG{
 
// dp array to store the
// ans for max 20 elements
static bool []dp = new bool[1 << 20];
 
// To check whether the
// number is prime or not
static bool isprime(int n)
{
    if (n == 1)
        return false;
 
    for(int i = 2; i * i <= n; i++)
    {
       if (n % i == 0)
       {
           return false;
       }
    }
    return true;
}
 
// Function to check whether the
// array can be modify so that
// there are only primes
static bool solve(int []arr, int curr,
                  int mask, int n)
{
 
    // If curr is prime and all
    // elements are visited,
    // return true
    if (isprime(curr))
    {
        if (mask == (1 << n) - 1)
        {
            return true;
        }
 
        // If all elements are not
        // visited, set curr=0, to
        // search for new prime sum
        curr = 0;
    }
 
    // If all elements are visited
    if (mask == (1 << n) - 1)
    {
 
        // If the current sum is
        // not prime return false
        if (!isprime(curr))
        {
            return false;
        }
    }
 
    // If this state is already
    // calculated, return the
    // answer directly
    if (dp[mask])
        return dp[mask];
 
    // Try all state of mask
    for(int i = 0; i < n; i++)
    {
        
       // If ith index is not set
       if ((mask & (1 << i)) == 0)
       {
            
           // Add the current element
           // and set ith index and recur
           if (solve(arr, curr + arr[i],
                     mask | 1 << i, n))
           {
                
               // If subset can be formed
               // then return true
               return true;
           }
       }
    }
     
    // After every possibility of mask,
    // if the subset is not formed,
    // return false by memoizing.
    return dp[mask] = false;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 6, 7, 13 };
    int n = arr.Length;
     
    if(solve(arr, 0, 0, n))
    {
        Console.Write("YES");
    }
    else
    {
        Console.Write("NO");
    }
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
// Javascript program to find the
// array of primes
 
// DP array to store the
// ans for max 20 elements
dp = Array(1 << 20).fill(0);
 
// To check whether the
// number is prime or not
function isprime(n)
{
    if (n == 1)
        return false;
         
    for(var i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}
 
// Function to check whether the
// array can be modify so that
// there are only primes
function solve(arr, curr, mask, n)
{
 
    // If curr is prime and all
    // elements are visited,
    // return true
    if (isprime(curr))
    {
        if (mask == (1 << n) - 1)
        {
            return true;
        }
 
        // If all elements are not
        // visited, set curr=0, to
        // search for new prime sum
        curr = 0;
    }
 
    // If all elements are visited
    if (mask == (1 << n) - 1)
    {
 
        // If the current sum is
        // not prime return false
        if (!isprime(curr))
        {
            return false;
        }
    }
 
    // If this state is already
    // calculated, return the
    // answer directly
    if (dp[mask])
        return dp[mask];
 
    // Try all state of mask
    for(var i = 0; i < n; i++)
    {
         
        // If ith index is not set
        if (!(mask & 1 << i))
        {
             
            // Add the current element
            // and set ith index and recur
            if (solve(arr, curr + arr[i],
                       mask | 1 << i, n))
            {
                 
                // If subset can be formed
                // then return true
                return true;
            }
        }
    }
     
    // After every possibility of mask,
    // if the subset is not formed,
    // return false by memoizing.
    return dp[mask] = false;
}
 
// Driver code
var arr = [ 3, 6, 7, 13 ]
var n = arr.length
 
if (solve(arr, 0, 0, n))
{
    document.write("YES");
}
else
{
    document.write("NO");
}
 
// This code is contributed by rutvik_56
     
</script>

YES

Complejidad del tiempo: O(N ² )

Espacio Auxiliar: O(2 ¹⁹ ).