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 primosEntrada: {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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
YES
Complejidad del tiempo: O(N 2 )
Espacio Auxiliar: O(2 19 ).
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA