Dado un entero positivo N , la tarea es contar el número de números de N dígitos que contienen todos los números primos de un solo dígito .
Ejemplos:
Entrada: N = 4
Salida: 24
Explicación: El número de números primos de un solo dígito es 4, es decir, {2, 3, 5, 7}. ¡Por lo tanto, el número de formas de organizar 4 números en 4 lugares es 4! = 24.Entrada: N = 5
Salida: 936
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 que contienen todos los números primos de un solo dígito . Después de verificar todos los números, imprima el valor del conteo como el conteo total de números resultante.
Complejidad temporal: O(N *10 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque tiene subproblemas superpuestos y una subestructura óptima. Los subproblemas se pueden almacenar en la tabla dp[][] usando memoization donde dp[index][mask] almacena la respuesta desde la posición del índice th hasta el final, donde mask se usa para almacenar el recuento de números primos distintos incluidos hasta ahora. Siga los pasos a continuación para resolver el problema:
- Inicialice una array multidimensional global dp[100][1<<4] con todos los valores como -1 que almacena el resultado de cada llamada recursiva .
- Indexe todos los números primos de un solo dígito en orden ascendente usando un HashMap .
- Defina una función recursiva , digamos countOfNumbers(index, mask, N) realizando los siguientes pasos.
- Si el valor de un índice es igual a (N + 1),
- Cuente el número de primos de un solo dígito distintos incluidos al encontrar el recuento de bits establecidos en la máscara.
- Si el conteo es igual a 4 , 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[index][mask] ya se calculó, devuelva este valor dp[index][mask] .
- Si el índice actual es 1 , entonces se puede colocar cualquier dígito de [1-9] y si N = 1 , entonces también se puede colocar 0 .
- Para todos los demás índices, se puede colocar cualquier dígito de [0-9] .
- Si el dígito actual colocado es un número primo , establezca el índice del número primo en 1 en la máscara de bits.
- Después de realizar una ubicación válida, llame recursivamente a la función countOfNumbers for (index + 1) .
- Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.
- Si el valor de un índice es igual a (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++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the dp-states
int dp[100][1 << 4];
// Stores the index of prime numbers
map<int, int> primeIndex;
int countOfNumbers(int index, int mask, int N)
{
// If index = N+1
if (index == N + 1) {
// Find count of distinct
// prime numbers by counting
// number of set bits.
int countOfPrimes = __builtin_popcount(mask);
// If count of distinct
// prime numbers is equal to 4
// return 1.
if (countOfPrimes == 4) {
return 1;
}
return 0;
}
int& val = dp[index][mask];
// If the state has
// already been computed
if (val != -1) {
return val;
}
val = 0;
// If current position is 1,
// then any digit from [1-9] can be placed.
// If N = 1, 0 can be also placed.
if (index == 1) {
for (int digit = (N == 1 ? 0 : 1); digit <= 9;
++digit) {
// If the digit is a prime number,
// set the index of the
// digit to 1 in the bitmask.
if (primeIndex.find(digit)
!= primeIndex.end()) {
val += countOfNumbers(
index + 1,
mask | (1 << primeIndex[digit]), N);
}
else {
val += countOfNumbers(index + 1, mask, N);
}
}
}
// For remaining positions,
// any digit from [0-9] can be placed
else {
for (int digit = 0; digit <= 9; ++digit) {
// If the digit is a prime number,
// set the index of the
// digit to 1 in the bitmask.
if (primeIndex.find(digit)
!= primeIndex.end()) {
val += countOfNumbers(
index + 1,
mask | (1 << primeIndex[digit]), N);
}
else {
val += countOfNumbers(index + 1, mask, N);
}
}
}
// Return the answer.
return val;
}
// Driver Code
int main()
{
// Initializing dp array with -1.
memset(dp, -1, sizeof dp);
// Indexing prime numbers in
// ascending order
primeIndex[2] = 0;
primeIndex[3] = 1;
primeIndex[5] = 2;
primeIndex[7] = 3;
// Given Input
int N = 4;
// Function call.
cout << countOfNumbers(1, 0, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
public static int[][] dp = new int[100][(1 << 4)];
// Stores the index of prime numbers
public static HashMap<Integer,
Integer> primeIndex = new HashMap<>();
public static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
public static int countOfNumbers(int index, int mask,
int N)
{
// If index = N+1
if (index == N + 1)
{
// Find count of distinct
// prime numbers by counting
// number of set bits.
int countOfPrimes = countSetBits(mask);
// If count of distinct
// prime numbers is equal to 4
// return 1.
if (countOfPrimes == 4)
{
return 1;
}
return 0;
}
int val = dp[index][mask];
// If the state has
// already been computed
if (val != -1)
{
return val;
}
val = 0;
// If current position is 1, then any
// digit from [1-9] can be placed.
// If N = 1, 0 can be also placed.
if (index == 1)
{
for(int digit = (N == 1 ? 0 : 1);
digit <= 9; ++digit)
{
// If the digit is a prime number,
// set the index of the digit to 1
// in the bitmask.
if (primeIndex.containsKey(digit))
{
int newMask = mask | (1 << primeIndex.get(digit));
val += countOfNumbers(index + 1,
newMask, N);
}
else
{
val += countOfNumbers(index + 1, mask, N);
}
}
}
// For remaining positions,
// any digit from [0-9] can be placed
else
{
for(int digit = 0; digit <= 9; ++digit)
{
// If the digit is a prime number,
// set the index of the digit to 1
// in the bitmask.
if (primeIndex.containsKey(digit))
{
int newMask = mask | (1 << primeIndex.get(digit));
val += countOfNumbers(index + 1, newMask, N);
}
else
{
val += countOfNumbers(index + 1, mask, 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 < (1 << 4); j++)
{
dp[i][j] = -1;
}
}
// Indexing prime numbers in
// ascending order
primeIndex.put(2, 0);
primeIndex.put(3, 1);
primeIndex.put(5, 2);
primeIndex.put(7, 3);
// Given Input
int N = 4;
// Function call
System.out.println(countOfNumbers(1, 0, N));
}
}
// This code is contributed by maddler
Python3
# Python3 program for the above approach
# Stores the dp-states
dp = [[-1 for i in range(1<<4)] for j in range(100)]
# Stores the index of prime numbers
primeIndex = {}
def countSetBits(n):
count = 0
while (n):
count += n & 1
n >>= 1
return count
def countOfNumbers(index, mask, N):
# If index = N+1
if (index == N + 1):
# Find count of distinct
# prime numbers by counting
# number of set bits.
countOfPrimes = countSetBits(mask);
# If count of distinct
# prime numbers is equal to 4
# return 1.
if (countOfPrimes == 4):
return 1
return 0
val = dp[index][mask]
# If the state has
# already been computed
if (val != -1):
return val
val = 0
# If current position is 1,
# then any digit from [1-9] can be placed.
# If N = 1, 0 can be also placed.
if (index == 1):
digit = 0 if N == 1 else 1
while(digit <= 9):
# If the digit is a prime number,
# set the index of the
# digit to 1 in the bitmask.
if (digit in primeIndex):
val += countOfNumbers(index + 1,mask | (1 << primeIndex[digit]), N)
else:
val += countOfNumbers(index + 1, mask, N)
digit += 1
# For remaining positions,
# any digit from [0-9] can be placed
else:
for digit in range(10):
# If the digit is a prime number,
# set the index of the
# digit to 1 in the bitmask.
if (digit in primeIndex):
val += countOfNumbers(index + 1,mask | (1 << primeIndex[digit]), N)
else:
val += countOfNumbers(index + 1, mask, N)
# Return the answer.
return val
# Driver Code
if __name__ == '__main__':
# Initializing dp array with -1.
# Indexing prime numbers in
# ascending order
primeIndex[2] = 0
primeIndex[3] = 1
primeIndex[5] = 2
primeIndex[7] = 3
# Given Input
N = 4
# Function call.
print(countOfNumbers(1, 0, N))
# This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
public static int[,] dp = new int[100,(1 << 4)];
// Stores the index of prime numbers
public static Dictionary<int,int> primeIndex = new Dictionary<int,int>();
public static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
public static int countOfNumbers(int index, int mask,
int N)
{
// If index = N+1
if (index == N + 1)
{
// Find count of distinct
// prime numbers by counting
// number of set bits.
int countOfPrimes = countSetBits(mask);
// If count of distinct
// prime numbers is equal to 4
// return 1.
if (countOfPrimes == 4)
{
return 1;
}
return 0;
}
int val = dp[index,mask];
// If the state has
// already been computed
if (val != -1)
{
return val;
}
val = 0;
// If current position is 1, then any
// digit from [1-9] can be placed.
// If N = 1, 0 can be also placed.
if (index == 1)
{
for(int digit = (N == 1 ? 0 : 1);
digit <= 9; ++digit)
{
// If the digit is a prime number,
// set the index of the digit to 1
// in the bitmask.
if (primeIndex.ContainsKey(digit))
{
int newMask = mask | (1 << primeIndex[digit]);
val += countOfNumbers(index + 1,
newMask, N);
}
else
{
val += countOfNumbers(index + 1, mask, N);
}
}
}
// For remaining positions,
// any digit from [0-9] can be placed
else
{
for(int digit = 0; digit <= 9; ++digit)
{
// If the digit is a prime number,
// set the index of the digit to 1
// in the bitmask.
if (primeIndex.ContainsKey(digit))
{
int newMask = mask | (1 << primeIndex[digit]);
val += countOfNumbers(index + 1, newMask, N);
}
else
{
val += countOfNumbers(index + 1, mask, 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 < (1 << 4); j++)
{
dp[i,j] = -1;
}
}
// Indexing prime numbers in
// ascending order
primeIndex.Add(2, 0);
primeIndex.Add(3, 1);
primeIndex.Add(5, 2);
primeIndex.Add(7, 3);
// Given Input
int N = 4;
// Function call
Console.WriteLine(countOfNumbers(1, 0, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
let dp = new Array(100).fill(0).map(() => new Array(1 << 4));
// Stores the index of prime numbers
let primeIndex = new Map();
function countSetBits(n) {
let count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count;
}
function countOfNumbers(index, mask, N) {
// If index = N+1
if (index == N + 1) {
// Find count of distinct
// prime numbers by counting
// number of set bits.
let countOfPrimes = countSetBits(mask);
// If count of distinct
// prime numbers is equal to 4
// return 1.
if (countOfPrimes == 4) {
return 1;
}
return 0;
}
let val = dp[index][mask];
// If the state has
// already been computed
if (val != -1) {
return val;
}
val = 0;
// If current position is 1, then any
// digit from [1-9] can be placed.
// If N = 1, 0 can be also placed.
if (index == 1) {
for (let digit = N == 1 ? 0 : 1; digit <= 9; ++digit) {
// If the digit is a prime number,
// set the index of the digit to 1
// in the bitmask.
if (primeIndex.has(digit)) {
let newMask = mask | (1 << primeIndex.get(digit));
val += countOfNumbers(index + 1, newMask, N);
} else {
val += countOfNumbers(index + 1, mask, N);
}
}
}
// For remaining positions,
// any digit from [0-9] can be placed
else {
for (let digit = 0; digit <= 9; ++digit) {
// If the digit is a prime number,
// set the index of the digit to 1
// in the bitmask.
if (primeIndex.has(digit)) {
let newMask = mask | (1 << primeIndex.get(digit));
val += countOfNumbers(index + 1, newMask, N);
} else {
val += countOfNumbers(index + 1, mask, N);
}
}
}
// Return the answer.
return val;
}
// Driver Code
// Initializing dp array with -1.
for (let i = 0; i < 100; i++) {
for (let j = 0; j < 1 << 4; j++) {
dp[i][j] = -1;
}
}
// Indexing prime numbers in
// ascending order
primeIndex.set(2, 0);
primeIndex.set(3, 1);
primeIndex.set(5, 2);
primeIndex.set(7, 3);
// Given Input
let N = 4;
// Function call
document.write(countOfNumbers(1, 0, N));
// This code is contributed by gfgking
</script>
Producción
24
Complejidad de Tiempo: O(N *10 * 2 4 )
Espacio Auxiliar: O(N * 2 4 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA