Dado un entero positivo N , la tarea es contar el número de números de N dígitos cuya suma de dígitos es un número primo .
Ejemplos:
Entrada: N = 1
Salida: 4
Explicación: [2, 3, 5, 7] son números de un solo dígito cuya suma de dígitos es igual a un número primo.Entrada: N = 2
Salida: 33
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los números posibles de N dígitos y contar aquellos números cuya suma de dígitos es un número primo . Después de verificar todos los números, imprima el valor del conteo como el conteo total de números resultante.
Complejidad de tiempo: O (N * 10 N )
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica recursiva porque el problema anterior tiene subproblemas superpuestos y una subestructura óptima . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D global dp[N+1][N*10] con todos los valores como -1 que almacena el resultado de cada llamada recursiva .
- Calcule números primos hasta (N * 10) números usando la criba de Eratóstenes .
- Defina una función recursiva, digamos countOfNumbers(index, sum, N) realizando los siguientes pasos.
- Si el valor del índice es N+1 ,
- Si la suma es un número primo , devuelve 1 ya que se ha formado un número válido de N dígitos.
- De lo contrario, devuelve 0 .
- Si el resultado del estado dp[índice][suma] ya se calculó, devuelve este valor dp[índice][suma].
- Si el índice actual es 1 , se puede colocar cualquier dígito del [1 al 9] ; de lo contrario, se puede colocar el [0 al 9] .
- Después de realizar una colocación válida de dígitos, llame recursivamente a la función countOfNumbers para el siguiente índice y sume todos los resultados recursivos pendientes en la variable val .
- Almacene el valor de val en el estado actual de la tabla dp[index][sum] .
- Devuelve el valor de resultado de este estado a su llamada recursiva principal.
- Si el valor del índice es N+1 ,
- Imprime el valor devuelto por la función countOfNumbers(1, 0, N) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Stores the dp states
int dp[100][1000];
// Check if a number is
// a prime or not
bool prime[1005];
// Function to generate all prime numbers
// that are less than or equal to n
void SieveOfEratosthenes(int n)
{
// Base cases.
prime[0] = prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples
// of as non-prime
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find the count of N-digit numbers
// such that the sum of digits is a prime number
int countOfNumbers(int index, int sum, int N)
{
// If end of array is reached
if (index == N + 1) {
// If the sum is equal to a prime number
if (prime[sum] == true) {
return 1;
}
// Otherwise
return 0;
}
int& val = dp[index][sum];
// If the dp-states are already computed
if (val != -1) {
return val;
}
val = 0;
// If index = 1, any digit from [1 - 9] can be placed.
// If N = 1, 0 also can be placed.
if (index == 1) {
for (int digit = (N == 1 ? 0 : 1); digit <= 9;
++digit) {
val += countOfNumbers(index + 1, sum + digit,
N);
}
}
// Otherwise, any digit from [0 - 9] can be placed.
else {
for (int digit = 0; digit <= 9; ++digit) {
val += countOfNumbers(index + 1, sum + digit,
N);
}
}
// Return the answer.
return val;
}
// Driver Code
int main()
{
// Initializing dp array with -1
memset(dp, -1, sizeof dp);
// Initializing prime array to true
memset(prime, true, sizeof(prime));
// Find all primes less than or equal to 1000,
// which is sufficient for N upto 100
SieveOfEratosthenes(1000);
// Given Input
int N = 6;
// Function call
cout << countOfNumbers(1, 0, N);
return 0;
}
Java
import java.util.Arrays;
class GFG{
// Stores the dp states
public static int[][] dp = new int[100][1000];
// Check if a number is
// a prime or not
public static boolean[] prime = new boolean[1005];
// Function to generate all prime numbers
// that are less than or equal to n
public static void SieveOfEratosthenes(int n)
{
// Base cases.
prime[0] = prime[1] = false;
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples
// of as non-prime
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find the count of N-digit numbers
// such that the sum of digits is a prime number
public static int countOfNumbers(int index, int sum,
int N)
{
// If end of array is reached
if (index == N + 1)
{
// If the sum is equal to a prime number
if (prime[sum] == true)
{
return 1;
}
// Otherwise
return 0;
}
int val = dp[index][sum];
// If the dp-states are already computed
if (val != -1)
{
return val;
}
val = 0;
// If index = 1, any digit from [1 - 9] can be placed.
// If N = 1, 0 also can be placed.
if (index == 1)
{
for(int digit = (N == 1 ? 0 : 1);
digit <= 9; ++digit)
{
val += countOfNumbers(index + 1,
sum + digit, N);
}
}
// Otherwise, any digit from [0 - 9] can be placed.
else
{
for(int digit = 0; digit <= 9; ++digit)
{
val += countOfNumbers(index + 1,
sum + digit, N);
}
}
// Return the answer.
return val;
}
// Driver Code
public static void main(String args[])
{
// Initializing dp array with -1
for(int[] row : dp)
Arrays.fill(row, -1);
// Initializing prime array to true
Arrays.fill(prime, true);
// Find all primes less than or equal to 1000,
// which is sufficient for N upto 100
SieveOfEratosthenes(1000);
// Given Input
int N = 6;
// Function call
System.out.println(countOfNumbers(1, 0, N));
}
}
// This code is contributed by gfgking
Python3
# Python program for the above approach # Stores the dp states dp = [[-1]*100]*1000 # Check if a number is # a prime or not prime = [True] * 1005 # Function to generate all prime numbers # that are less than or equal to n def SieveOfEratosthenes(n) : # Base cases. prime[0] = prime[1] = False p = 2 while(p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Update all multiples # of as non-prime for i in range(p * p, n+1, p) : prime[i] = False p += 1 # Function to find the count of N-digit numbers # such that the sum of digits is a prime number def countOfNumbers(index, sum, N) : # If end of array is reached if (index == N + 1) : # If the sum is equal to a prime number if (prime[sum] == True) : return 1 # Otherwise return 0 val = dp[index][sum] # If the dp-states are already computed if (val != -1) : return val val = 0 # If index = 1, any digit from [1 - 9] can be placed. # If N = 1, 0 also can be placed. if (index == 1) : for digit in range(((0, 1) [N == 1])+1, 10, 1) : val += countOfNumbers(index + 1, sum + digit, N) # Otherwise, any digit from [0 - 9] can be placed. else : for digit in range(0, 10, 1) : val += countOfNumbers(index + 1, sum + digit, N) # Return the answer. return val # Driver Code # Find all primes less than or equal to 1000, # which is sufficient for N upto 100 SieveOfEratosthenes(1000) # Given Input N = 6 # Function call print(countOfNumbers(1, 0, N)) # This code is contributed by avijitmondal1998.
C#
using System;
public class GFG{
// Stores the dp states
public static int[,] dp = new int[100,1000];
// Check if a number is
// a prime or not
public static bool[] prime = new bool[1005];
// Function to generate all prime numbers
// that are less than or equal to n
public static void SieveOfEratosthenes(int n)
{
// Base cases.
prime[0] = prime[1] = false;
for(int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples
// of as non-prime
for(int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find the count of N-digit numbers
// such that the sum of digits is a prime number
public static int countOfNumbers(int index, int sum,
int N)
{
// If end of array is reached
if (index == N + 1)
{
// If the sum is equal to a prime number
if (prime[sum] == true)
{
return 1;
}
// Otherwise
return 0;
}
int val = dp[index,sum];
// If the dp-states are already computed
if (val != -1)
{
return val;
}
val = 0;
// If index = 1, any digit from [1 - 9] can be placed.
// If N = 1, 0 also can be placed.
if (index == 1)
{
for(int digit = (N == 1 ? 0 : 1);
digit <= 9; ++digit)
{
val += countOfNumbers(index + 1,
sum + digit, N);
}
}
// Otherwise, any digit from [0 - 9] can be placed.
else
{
for(int digit = 0; digit <= 9; ++digit)
{
val += countOfNumbers(index + 1,
sum + digit, N);
}
}
// Return the answer.
return val;
}
// Driver Code
public static void Main(String []args)
{
// Initializing dp array with -1
for(int i = 0; i < 100; i++)
{
for (int j = 0; j < 1000; j++) {
dp[i,j] = -1;
}
}
// Initializing prime array to true
for (int i = 0; i < prime.Length; i++)
prime[i] = true;
// Find all primes less than or equal to 1000,
// which is sufficient for N upto 100
SieveOfEratosthenes(1000);
// Given Input
int N = 6;
// Function call
Console.WriteLine(countOfNumbers(1, 0, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Stores the dp states
let dp = new Array(100).fill(0).map(() =>
new Array(1000).fill(-1));
// Check if a number is
// a prime or not
let prime = new Array(1005).fill(true);
// Function to generate all prime numbers
// that are less than or equal to n
function SieveOfEratosthenes(n)
{
// Base cases.
prime[0] = prime[1] = false;
for(let p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples
// of as non-prime
for(let i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
// Function to find the count of N-digit numbers
// such that the sum of digits is a prime number
function countOfNumbers(index, sum, N)
{
// If end of array is reached
if (index == N + 1)
{
// If the sum is equal to a prime number
if (prime[sum] == true)
{
return 1;
}
// Otherwise
return 0;
}
let val = dp[index][sum];
// If the dp-states are already computed
if (val != -1)
{
return val;
}
val = 0;
// If index = 1, any digit from [1 - 9] can
// be placed. If N = 1, 0 also can be placed.
if (index == 1)
{
for(let digit = N == 1 ? 0 : 1;
digit <= 9; ++digit)
{
val += countOfNumbers(index + 1,
sum + digit, N);
}
}
// Otherwise, any digit from [0 - 9]
// can be placed.
else
{
for(let digit = 0; digit <= 9; ++digit)
{
val += countOfNumbers(index + 1,
sum + digit, N);
}
}
// Return the answer.
return val;
}
// Driver Code
// Find all primes less than or equal to 1000,
// which is sufficient for N upto 100
SieveOfEratosthenes(1000);
// Given Input
let N = 6;
// Function call
document.write(countOfNumbers(1, 0, N));
// This code is contributed by gfgking
</script>
Producción:
222638
Complejidad de Tiempo: O(N 2 * 10)
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA