Dado un entero positivo N , la tarea es contar el número de números de N dígitos de modo que el recuento de dígitos impares y pares distintos en el número sea el mismo.
Ejemplos:
Entrada: N = 2
Salida: 45
Explicación:
Para un número de 2 dígitos, para satisfacer la condición, el primer dígito puede ser par y el segundo impar, o el segundo dígito puede ser impar y el primero par. Para el primer caso hay (4 X 5) = 20 posibilidades y para el segundo caso hay (5 X 5) = 25 posibilidades. Por lo tanto, la respuesta es 45.Entrada: N = 3
Salida: 135
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los números de N dígitos posibles y contar aquellos números donde el número de dígitos pares e impares distintos es el mismo. 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 el problema anterior tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la memorización de la tabla dp[][][] donde dp[index][ evenMask ][oddMask] almacena la respuesta desde la i -ésima posición del índice hasta el final, donde evenMask se utiliza para determinar el número de pares distintos . dígitos en el número y oddMask se usa para determinar el número de dígitos impares distintos en el número usando una máscara de bits . Siga los pasos a continuación para resolver el problema:
- Inicialice una array multidimensional global dp[100][1<<5][1<<5] con todos los valores como -1 que almacena el resultado de cada llamada recursiva.
- Defina una función recursiva , digamos countOfNumbers(index, evenMask, oddMask, N) realizando los siguientes pasos
- Si el valor de un índice es igual a (N + 1),
- Calcule el recuento de bits establecidos en evenMask y oddMask .
- Si tienen el mismo conteo, entonces el número de dígitos pares e impares distintos es el mismo y, por lo tanto, devuelven 1 como un número válido de N dígitos que se ha formado.
- De lo contrario, devuelve 0 .
- Si el resultado del estado dp[index][evenMask][oddMask] ya se calculó, devuelve este valor dp[index][evenMask][oddMask] .
- 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] .
- Para cualquier dígito colocado, establezca el (dígito / 2) th bit de evenMask o oddMask en 1 dependiendo de la paridad del dígito. Denota que el dígito particular está presente en el número. Dado que estamos dividiendo el dígito por 2 , la máscara de bits de tamaño (1 << 5) es suficiente para cada máscara impar y máscara par .
- 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),
- Después de completar los pasos anteriores, imprima el valor devuelto por la función countOfNumbers(1, 0, 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 << 5][1 << 5];
// Recursive Function to find number
// of N-digit numbers which has equal
// count of distinct odd & even digits
int countOfNumbers(int index, int evenMask,
int oddMask, int N)
{
// If index is N + 1
if (index == N + 1) {
// Find the count of set bits
// in the evenMask
int countOfEvenDigits
= __builtin_popcount(evenMask);
// Find the count of set bits
// in the oddMask
int countOfOddDigits
= __builtin_popcount(oddMask);
// If the count of set bits in both
// masks are equal then return 1
// as they have equal number of
// distinct odd and even digits
if (countOfOddDigits
== countOfEvenDigits) {
return 1;
}
return 0;
}
int& val = dp[index][evenMask][oddMask];
// 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 digit is odd
if (digit & 1) {
// Set the (digit/2)th bit
// of the oddMask
val += countOfNumbers(
index + 1, evenMask,
oddMask | (1 << (digit / 2)), N);
}
// Set the (digit/2)th bit
// of the number evenMask
else {
val += countOfNumbers(
index + 1,
evenMask | (1 << (digit / 2)),
oddMask, N);
}
}
}
// For remaining positions, any
// digit from [0-9] can be placed
else {
for (int digit = 0;
digit <= 9; ++digit) {
// If digit is odd
if (digit & 1) {
// Set the (digit/2)th
// bit of oddMask
val += countOfNumbers(
index + 1, evenMask,
oddMask | (1 << (digit / 2)), N);
}
else {
// Set the (digit/2)th
// bit of evenMask
val += countOfNumbers(
index + 1,
evenMask | (1 << (digit / 2)),
oddMask, N);
}
}
}
// Return the answer
return val;
}
// Function to find number of N-digit
// numbers which has equal count of
// distinct odd and even digits
void countNDigitNumber(int N)
{
// Initialize dp array with -1
memset(dp, -1, sizeof dp);
// Function Call
cout << countOfNumbers(1, 0, 0, N);
}
// Driver Code
int main()
{
int N = 3;
countNDigitNumber(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Stores the dp-states
static int[][][] dp = new int[100][1 << 5][1 << 5];
// Returns number of set bits in a number
static int __builtin_popcount(int n)
{
int d, t = 0;
while(n > 0)
{
d = n % 2;
n = n / 2;
if (d == 1)
t++;
}
return t;
}
// Recursive Function to find number
// of N-digit numbers which has equal
// count of distinct odd & even digits
static int countOfNumbers(int index, int evenMask,
int oddMask, int N)
{
// If index is N + 1
if (index == N + 1)
{
// Find the count of set bits
// in the evenMask
int countOfEvenDigits = __builtin_popcount(evenMask);
// Find the count of set bits
// in the oddMask
int countOfOddDigits = __builtin_popcount(oddMask);
// If the count of set bits in both
// masks are equal then return 1
// as they have equal number of
// distinct odd and even digits
if (countOfOddDigits == countOfEvenDigits)
{
return 1;
}
return 0;
}
int val = dp[index][evenMask][oddMask];
// 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 digit is odd
if ((digit & 1) != 0)
{
// Set the (digit/2)th bit
// of the oddMask
val += countOfNumbers(
index + 1, evenMask,
oddMask | (1 << (digit / 2)), N);
}
// Set the (digit/2)th bit
// of the number evenMask
else
{
val += countOfNumbers(
index + 1,
evenMask | (1 << (digit / 2)),
oddMask, N);
}
}
}
// For remaining positions, any
// digit from [0-9] can be placed
else
{
for(int digit = 0; digit <= 9; ++digit)
{
// If digit is odd
if ((digit & 1) != 0)
{
// Set the (digit/2)th
// bit of oddMask
val += countOfNumbers(
index + 1, evenMask,
oddMask | (1 << (digit / 2)), N);
}
else
{
// Set the (digit/2)th
// bit of evenMask
val += countOfNumbers(
index + 1,
evenMask | (1 << (digit / 2)),
oddMask, N);
}
}
}
// Return the answer
return val;
}
// Function to find number of N-digit
// numbers which has equal count of
// distinct odd and even digits
static void countNDigitNumber(int N)
{
// Initialize dp array with -1
for(int i = 0; i < 100; i++)
{
for(int j = 0; j < (1 << 5); j++)
{
for(int k = 0; k < (1 << 5); k++)
{
dp[i][j][k] = -1;
}
}
}
// Function Call
System.out.println(countOfNumbers(1, 0, 0, N));
}
// Driver code
public static void main(String[] args)
{
int N = 3;
countNDigitNumber(N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python program for the above approach: ## Stores the dp-states dp = [] # Function to count set bits in an integer # in Python def __builtin_popcount(num): # convert given number into binary # output will be like bin(11)=0b1101 binary = bin(num) # now separate out all 1's from binary string # we need to skip starting two characters # of binary string i.e; 0b setBits = [ones for ones in binary[2:] if ones=='1'] return len(setBits) ## Recursive Function to find number ## of N-digit numbers which has equal ## count of distinct odd & even digits def countOfNumbers(index, evenMask, oddMask, N): ## If index is N + 1 if (index == N + 1): ## Find the count of set bits ## in the evenMask countOfEvenDigits = __builtin_popcount(evenMask); ## Find the count of set bits ## in the oddMask countOfOddDigits = __builtin_popcount(oddMask); ## If the count of set bits in both ## masks are equal then return 1 ## as they have equal number of ## distinct odd and even digits if (countOfOddDigits == countOfEvenDigits): return 1 return 0 val = dp[index][evenMask][oddMask] ## 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): st = 1 if(N == 1): st = 0 for digit in range(st, 10): ## If digit is odd if (digit & 1) == 1: ## Set the (digit/2)th bit ## of the oddMask val += countOfNumbers(index + 1, evenMask, oddMask | (1 << (digit // 2)), N) ## Set the (digit/2)th bit ## of the number evenMask else: val += countOfNumbers(index + 1, evenMask | (1 << (digit // 2)), oddMask, N) ## For remaining positions, any ## digit from [0-9] can be placed else: for digit in range(10): ## If digit is odd if (digit & 1) == 1: ## Set the (digit/2)th ## bit of oddMask val += countOfNumbers(index + 1, evenMask, oddMask | (1 << (digit // 2)), N) else: ## Set the (digit/2)th ## bit of evenMask val += countOfNumbers(index + 1, evenMask | (1 << (digit // 2)), oddMask, N) dp[index][evenMask][oddMask] = val ## Return the answer return val ## Function to find number of N-digit ## numbers which has equal count of ## distinct odd and even digits def countNDigitNumber(N): ## Initialize dp array with -1 for i in range(0, 100): dp.append([]) for j in range(0, 1 << 5): dp[i].append([]) for k in range(0, 1 << 5): dp[i][j].append(-1) ## Function Call print(countOfNumbers(1, 0, 0, N)) ## Driver code if __name__=='__main__': N = 3 countNDigitNumber(N)
C#
// C# program for the above approach
using System;
class GFG{
// Stores the dp-states
static int[,,] dp = new int[100, 1 << 5, 1 << 5];
// Returns number of set bits in a number
static int __builtin_popcount(int n)
{
int d, t = 0;
while(n > 0)
{
d = n % 2;
n = n / 2;
if (d == 1)
t++;
}
return t;
}
// Recursive Function to find number
// of N-digit numbers which has equal
// count of distinct odd & even digits
static int countOfNumbers(int index, int evenMask,
int oddMask, int N)
{
// If index is N + 1
if (index == N + 1)
{
// Find the count of set bits
// in the evenMask
int countOfEvenDigits = __builtin_popcount(evenMask);
// Find the count of set bits
// in the oddMask
int countOfOddDigits = __builtin_popcount(oddMask);
// If the count of set bits in both
// masks are equal then return 1
// as they have equal number of
// distinct odd and even digits
if (countOfOddDigits == countOfEvenDigits)
{
return 1;
}
return 0;
}
int val = dp[index, evenMask, oddMask];
// 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 digit is odd
if ((digit & 1) != 0)
{
// Set the (digit/2)th bit
// of the oddMask
val += countOfNumbers(
index + 1, evenMask,
oddMask | (1 << (digit / 2)), N);
}
// Set the (digit/2)th bit
// of the number evenMask
else
{
val += countOfNumbers(
index + 1,
evenMask | (1 << (digit / 2)),
oddMask, N);
}
}
}
// For remaining positions, any
// digit from [0-9] can be placed
else
{
for(int digit = 0; digit <= 9; ++digit)
{
// If digit is odd
if ((digit & 1) != 0)
{
// Set the (digit/2)th
// bit of oddMask
val += countOfNumbers(
index + 1, evenMask,
oddMask | (1 << (digit / 2)), N);
}
else
{
// Set the (digit/2)th
// bit of evenMask
val += countOfNumbers(
index + 1,
evenMask | (1 << (digit / 2)),
oddMask, N);
}
}
}
// Return the answer
return val;
}
// Function to find number of N-digit
// numbers which has equal count of
// distinct odd and even digits
static void countNDigitNumber(int N)
{
// Initialize dp array with -1
for(int i = 0; i < 100; i++)
{
for(int j = 0; j < (1 << 5); j++)
{
for(int k = 0; k < (1 << 5); k++)
{
dp[i, j, k] = -1;
}
}
}
// Function Call
Console.Write(countOfNumbers(1, 0, 0, N));
}
// Driver Code
public static void Main()
{
int N = 3;
countNDigitNumber(N);
}
}
// This code is contributed by target_2.
Javascript
<script>
// javascript program for the above approach
// Stores the dp-states
var dp = Array(100).fill().map(()=>Array(1 << 5).fill().map(()=>Array(1 << 5).fill(0)));
// Returns number of set bits in a number
function __builtin_popcount(n) {
var d, t = 0;
while (n > 0) {
d = n % 2;
n = parseInt(n / 2);
if (d == 1)
t++;
}
return t;
}
// Recursive Function to find number
// of N-digit numbers which has equal
// count of distinct odd & even digits
function countOfNumbers(index , evenMask , oddMask , N) {
// If index is N + 1
if (index == N + 1) {
// Find the count of set bits
// in the evenMask
var countOfEvenDigits = __builtin_popcount(evenMask);
// Find the count of set bits
// in the oddMask
var countOfOddDigits = __builtin_popcount(oddMask);
// If the count of set bits in both
// masks are equal then return 1
// as they have equal number of
// distinct odd and even digits
if (countOfOddDigits == countOfEvenDigits) {
return 1;
}
return 0;
}
var val = dp[index][evenMask][oddMask];
// 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 (digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) {
// If digit is odd
if ((digit & 1) != 0) {
// Set the (digit/2)th bit
// of the oddMask
val += countOfNumbers(index + 1, evenMask, oddMask | (1 << (digit / 2)), N);
}
// Set the (digit/2)th bit
// of the number evenMask
else {
val += countOfNumbers(index + 1, evenMask | (1 << (digit / 2)), oddMask, N);
}
}
}
// For remaining positions, any
// digit from [0-9] can be placed
else {
for (var digit = 0; digit <= 9; ++digit) {
// If digit is odd
if ((digit & 1) != 0) {
// Set the (digit/2)th
// bit of oddMask
val += countOfNumbers(index + 1, evenMask, oddMask | (1 << (digit / 2)), N);
} else {
// Set the (digit/2)th
// bit of evenMask
val += countOfNumbers(index + 1, evenMask | (1 << (digit / 2)), oddMask, N);
}
}
}
// Return the answer
return val;
}
// Function to find number of N-digit
// numbers which has equal count of
// distinct odd and even digits
function countNDigitNumber(N) {
// Initialize dp array with -1
for (var i = 0; i < 100; i++) {
for (var j = 0; j < (1 << 5); j++) {
for (var k = 0; k < (1 << 5); k++) {
dp[i][j][k] = -1;
}
}
}
// Function Call
document.write(countOfNumbers(1, 0, 0, N));
}
// Driver code
var N = 3;
countNDigitNumber(N);
// This code is contributed by gauravrajput1
</script>
Producción:
135
Complejidad de tiempo: O(N * 10 * 2 5 * 2 5 )
Espacio auxiliar: O (N * 2 5 * 2 5 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA