Encuentre el número mínimo de números primos de un solo dígito necesarios cuya suma sea igual a N.
Ejemplos:
Input: 11 Output: 3 Explanation: 5 + 3 + 3. Another possibility is 3 + 3 + 3 + 2, but it is not the minimal Input: 12 Output: 2 Explanation: 7 + 5
Enfoque: la programación dinámica se puede utilizar para resolver el problema anterior. Las observaciones son:
- Solo hay 4 números primos de un solo dígito {2, 3, 5, 7}.
- Si es posible hacer N sumando números primos de un solo dígito, entonces al menos uno de N-2, N-3, N-5 o N-7 también es accesible.
- El número mínimo de números primos de un solo dígito necesarios será uno más que el número mínimo de dígitos primos necesarios para formar uno de {N-2, N-3, N-5, N-7}.
Usando estas observaciones, construyó una recurrencia para resolver este problema. La recurrencia será:
dp[i] = 1 + min(dp[i-2], dp[i-3], dp[i-5], dp[i-7])
Para {2, 3, 5, 7}, la respuesta sería 1. Para cada otro número, usando la Observación 3, trate de encontrar el valor mínimo posible, si es posible.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find the minimum number of single
// digit prime numbers required which when summed
// equals to a given number N.
#include <bits/stdc++.h>
using namespace std;
// function to check if i-th
// index is valid or not
bool check(int i, int val)
{
if (i - val < 0)
return false;
return true;
}
// function to find the minimum number of single
// digit prime numbers required which when summed up
// equals to a given number N.
int MinimumPrimes(int n)
{
int dp[n + 1];
for (int i = 1; i <= n; i++)
dp[i] = 1e9;
dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1;
for (int i = 1; i <= n; i++) {
if (check(i, 2))
dp[i] = min(dp[i], 1 + dp[i - 2]);
if (check(i, 3))
dp[i] = min(dp[i], 1 + dp[i - 3]);
if (check(i, 5))
dp[i] = min(dp[i], 1 + dp[i - 5]);
if (check(i, 7))
dp[i] = min(dp[i], 1 + dp[i - 7]);
}
// Not possible
if (dp[n] == (1e9))
return -1;
else
return dp[n];
}
// Driver Code
int main()
{
int n = 12;
int minimal = MinimumPrimes(n);
if (minimal != -1)
cout << "Minimum number of single"
<< " digit primes required : "
<< minimal << endl;
else
cout << "Not possible";
return 0;
}
C
// C program to find the minimum number of single
// digit prime numbers required which when summed
// equals to a given number N.
#include <stdio.h>
#include <stdbool.h>
int min(int a, int b)
{
int min = a;
if(min > b)
min = b;
return min;
}
// function to check if i-th
// index is valid or not
bool check(int i, int val)
{
if (i - val < 0)
return false;
return true;
}
// function to find the minimum number of single
// digit prime numbers required which when summed up
// equals to a given number N.
int MinimumPrimes(int n)
{
int dp[n + 1];
for (int i = 1; i <= n; i++)
dp[i] = 1e9;
dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1;
for (int i = 1; i <= n; i++) {
if (check(i, 2))
dp[i] = min(dp[i], 1 + dp[i - 2]);
if (check(i, 3))
dp[i] = min(dp[i], 1 + dp[i - 3]);
if (check(i, 5))
dp[i] = min(dp[i], 1 + dp[i - 5]);
if (check(i, 7))
dp[i] = min(dp[i], 1 + dp[i - 7]);
}
// Not possible
if (dp[n] == (1e9))
return -1;
else
return dp[n];
}
// Driver Code
int main()
{
int n = 12;
int minimal = MinimumPrimes(n);
if (minimal != -1)
printf("Minimum number of single digit primes required : %d\n",minimal);
else
printf("Not possible");
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find the minimum number
// of single digit prime numbers required
// which when summed equals to a given
// number N.
class Geeks {
// function to check if i-th
// index is valid or not
static boolean check(int i, int val)
{
if (i - val < 0)
return false;
else
return true;
}
// function to find the minimum number
// of single digit prime numbers required
// which when summed up equals to a given
// number N.
static double MinimumPrimes(int n)
{
double[] dp;
dp = new double[n+1];
for (int i = 1; i <= n; i++)
dp[i] = 1e9;
dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1;
for (int i = 1; i <= n; i++) {
if (check(i, 2))
dp[i] = Math.min(dp[i], 1 + dp[i - 2]);
if (check(i, 3))
dp[i] = Math.min(dp[i], 1 + dp[i - 3]);
if (check(i, 5))
dp[i] = Math.min(dp[i], 1 + dp[i - 5]);
if (check(i, 7))
dp[i] = Math.min(dp[i], 1 + dp[i - 7]);
}
// Not possible
if (dp[n] == (1e9))
return -1;
else
return dp[n];
}
// Driver Code
public static void main(String args[])
{
int n = 12;
int minimal = (int)MinimumPrimes(n);
if (minimal != -1)
System.out.println("Minimum number of single "+
"digit primes required: "+minimal);
else
System.out.println("Not Possible");
}
}
// This code is contributed ankita_saini
Python 3
# Python3 program to find the minimum number
# of single digit prime numbers required
# which when summed equals to a given
# number N.
# function to check if i-th
# index is valid or not
def check(i,val):
if i-val<0:
return False
return True
# function to find the minimum number of single
# digit prime numbers required which when summed up
# equals to a given number N.
def MinimumPrimes(n):
dp=[10**9]*(n+1)
dp[0]=dp[2]=dp[3]=dp[5]=dp[7]=1
for i in range(1,n+1):
if check(i,2):
dp[i]=min(dp[i],1+dp[i-2])
if check(i,3):
dp[i]=min(dp[i],1+dp[i-3])
if check(i,5):
dp[i]=min(dp[i],1+dp[i-5])
if check(i,7):
dp[i]=min(dp[i],1+dp[i-7])
# Not possible
if dp[n]==10**9:
return -1
else:
return dp[n]
# Driver Code
if __name__ == "__main__":
n=12
minimal=MinimumPrimes(n)
if minimal!=-1:
print("Minimum number of single digit primes required : ",minimal)
else:
print("Not possible")
#This code is contributed Saurabh Shukla
C#
// C# program to find the
// minimum number of single
// digit prime numbers required
// which when summed equals to
// a given number N.
using System;
class GFG
{
// function to check if i-th
// index is valid or not
static Boolean check(int i,
int val)
{
if (i - val < 0)
return false;
else
return true;
}
// function to find the
// minimum number of single
// digit prime numbers
// required which when summed
// up equals to a given
// number N.
static double MinimumPrimes(int n)
{
double[] dp;
dp = new double[n + 1];
for (int i = 1; i <= n; i++)
dp[i] = 1e9;
dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1;
for (int i = 1; i <= n; i++)
{
if (check(i, 2))
dp[i] = Math.Min(dp[i], 1 +
dp[i - 2]);
if (check(i, 3))
dp[i] = Math.Min(dp[i], 1 +
dp[i - 3]);
if (check(i, 5))
dp[i] = Math.Min(dp[i], 1 +
dp[i - 5]);
if (check(i, 7))
dp[i] = Math.Min(dp[i], 1 +
dp[i - 7]);
}
// Not possible
if (dp[n] == (1e9))
return -1;
else
return dp[n];
}
// Driver Code
public static void Main(String []args)
{
int n = 12;
int minimal = (int)MinimumPrimes(n);
if (minimal != -1)
Console.WriteLine("Minimum number of single " +
"digit primes required: " +
minimal);
else
Console.WriteLine("Not Possible");
}
}
// This code is contributed
// by Ankita_Saini
PHP
<?php
// PHP program to find the minimum
// number of single digit prime
// numbers required which when summed
// equals to a given number N.
// function to check if i-th
// index is valid or not
function check($i, $val)
{
if ($i - $val < 0)
return false;
return true;
}
// function to find the minimum
// number of single digit prime
// numbers required which when
// summed up equals to a given
// number N.
function MinimumPrimes($n)
{
for ($i = 1; $i<= $n; $i++)
$dp[$i] = 1e9;
$dp[0] = $dp[2] = $dp[3] = $dp[5] = $dp[7] = 1;
for ($i = 1; $i <= $n; $i++)
{
if (check($i, 2))
$dp[$i] = min($dp[$i], 1 +
$dp[$i - 2]);
if (check($i, 3))
$dp[$i] = min($dp[$i], 1 +
$dp[$i - 3]);
if (check($i, 5))
$dp[$i] = min($dp[$i], 1 +
$dp[$i - 5]);
if (check($i, 7))
$dp[$i] = min($dp[$i], 1 +
$dp[$i - 7]);
}
// Not possible
if ($dp[$n] == (1e9))
return -1;
else
return $dp[$n];
}
// Driver Code
$n = 12;
$minimal = MinimumPrimes($n);
if ($minimal != -1)
{
echo("Minimum number of single " .
"digit primes required :");
echo( $minimal );
}
else
{
echo("Not possible");
}
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to find the minimum
// number of single digit prime
// numbers required which when summed
// equals to a given number N.
// function to check if i-th
// index is valid or not
function check(i, val)
{
if (i - val < 0)
return false;
return true;
}
// function to find the minimum
// number of single digit prime
// numbers required which when
// summed up equals to a given
// number N.
function MinimumPrimes(n)
{
let dp = new Array(n + 1)
for (let i = 1; i<= n; i++)
dp[i] = 1e9;
dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1;
for (let i = 1; i <= n; i++)
{
if (check(i, 2))
dp[i] = Math.min(dp[i], 1 +
dp[i - 2]);
if (check(i, 3))
dp[i] = Math.min(dp[i], 1 +
dp[i - 3]);
if (check(i, 5))
dp[i] = Math.min(dp[i], 1 +
dp[i - 5]);
if (check(i, 7))
dp[i] = Math.min(dp[i], 1 +
dp[i - 7]);
}
// Not possible
if (dp[n] == (1e9))
return -1;
else
return dp[n];
}
// Driver Code
let n = 12;
let minimal = MinimumPrimes(n);
if (minimal != -1)
{
document.write("Minimum number of single " + "digit primes required :");
document.write( minimal );
}
else
{
document.write("Not possible");
}
// This code is contributed
// by gfgking
</script>
Producción:
Minimum number of single digit primes required : 2
Complejidad de tiempo: O(N)
Nota: En caso de consultas múltiples, la array dp[] se puede calcular previamente y podemos responder cada consulta en O(1).
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA