Dado un entero positivo N , la tarea es contar el número de números de N dígitos de modo que el AND bit a bit de los dígitos adyacentes sea igual a 0.
Ejemplos:
Entrada: N = 1
Salida: 10
Explicación: Todos los números del 0 al 9 cumplen la condición dada ya que solo hay un dígito.Entrada: N = 3
Salida: 264
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre todos los números de N dígitos posibles y contar aquellos números cuyo AND bit a bit de dígitos adyacentes es 0 . Después de verificar todos los números, imprima el valor de conteo como resultado.
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 tabla dp[][] utilizando la memorización donde dp[digit][prev] almacena la respuesta desde la posición del dígito th hasta el final, cuando el dígito anterior seleccionado es prev . Siga los pasos a continuación para resolver el problema:
- Defina una función recursiva , digamos countOfNumbers(digit, prev) realizando los siguientes pasos.
- Si el valor del dígito es igual a N + 1 , devuelva 1 ya que se forma un número válido de N dígitos .
- Si el resultado del estado dp[digit][prev] ya se calculó, devuelva este estado dp[digit][prev] .
- Si el dígito actual es 1 , entonces se puede colocar cualquier dígito de [1, 9] . Si N = 1 , entonces también se puede colocar 0 .
- De lo contrario, repita todos los números desde i = 0 hasta i = 9 y verifique si la condición ((i & prev) == 0) es válida o no y, en consecuencia, coloque los valores ‘i’ satisfactorios en la posición actual.
- Después de realizar una ubicación válida, llame recursivamente a la función countOfNumbers para el índice (dígito + 1) .
- Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.
- 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; int dp[100][10]; // Function to calculate count of 'N' digit // numbers such that bitwise AND of adjacent // digits is 0. int countOfNumbers(int digit, int prev, int n) { // If digit = n + 1, a valid // n-digit number has been formed if (digit == n + 1) { return 1; } // If the state has // already been computed int& val = dp[digit][prev]; 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 (digit == 1) { for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) { val += countOfNumbers(digit + 1, i, n); } } // For remaining positions, // any digit from [0-9] can be placed // after checking the conditions. else { for (int i = 0; i <= 9; ++i) { // Check if bitwise AND // of current digit and // previous digit is 0. if ((i & prev) == 0) { val += countOfNumbers(digit + 1, i, n); } } } // Return answer return val; } // Driver code int main() { // Initialize dp array with -1. memset(dp, -1, sizeof dp); // Given Input int N = 3; // Function call cout << countOfNumbers(1, 0, N) << endl; }
Java
// Java program for the above approach import java.util.*; class GFG{ static int dp[][] = new int[100][10]; // Function to calculate count of 'N' digit // numbers such that bitwise AND of adjacent // digits is 0. static int countOfNumbers(int digit, int prev, int n) { // If digit = n + 1, a valid // n-digit number has been formed if (digit == n + 1) { return 1; } // If the state has // already been computed int val = dp[digit][prev]; 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 (digit == 1) { for(int i = (n == 1 ? 0 : 1); i <= 9; ++i) { val += countOfNumbers(digit + 1, i, n); } } // For remaining positions, // any digit from [0-9] can be placed // after checking the conditions. else { for(int i = 0; i <= 9; ++i) { // Check if bitwise AND // of current digit and // previous digit is 0. if ((i & prev) == 0) { val += countOfNumbers(digit + 1, i, n); } } } // Return 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 < 10; j++) { dp[i][j] = -1; } } // Given Input int N = 3; // Function call System.out.println(countOfNumbers(1, 0, N)); } } // This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach dp = [[-1 for i in range(10)] for j in range(100)] val = 0 # Function to calculate count of 'N' digit # numbers such that bitwise AND of adjacent # digits is 0. def countOfNumbers(digit, prev, n): global val global dp # If digit = n + 1, a valid # n-digit number has been formed if (digit == n + 1): return 1 # If the state has # already been computed val = dp[digit][prev] 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 (digit == 1): i = 0 if n == 1 else 1 while (i <= 9): val += countOfNumbers(digit + 1, i, n) i += 1 # For remaining positions, # any digit from [0-9] can be placed # after checking the conditions. else: for i in range(10): # Check if bitwise AND # of current digit and # previous digit is 0. if ((i & prev) == 0): val += countOfNumbers(digit + 1, i, n) # Return answer return val # Driver code if __name__ == '__main__': # Given Input N = 3 # Function call print(countOfNumbers(1, 0, N)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach using System; class GFG { static int[,] dp = new int[100, 10]; // Function to calculate count of 'N' digit // numbers such that bitwise AND of adjacent // digits is 0. static int countOfNumbers(int digit, int prev, int n) { // If digit = n + 1, a valid // n-digit number has been formed if (digit == n + 1) { return 1; } // If the state has // already been computed int val = dp[digit, prev]; 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 (digit == 1) { for(int i = (n == 1 ? 0 : 1); i <= 9; ++i) { val += countOfNumbers(digit + 1, i, n); } } // For remaining positions, // any digit from [0-9] can be placed // after checking the conditions. else { for(int i = 0; i <= 9; ++i) { // Check if bitwise AND // of current digit and // previous digit is 0. if ((i & prev) == 0) { val += countOfNumbers(digit + 1, i, n); } } } // Return 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 < 10; j++) { dp[i, j] = -1; } } // Given Input int N = 3; // Function call Console.WriteLine(countOfNumbers(1, 0, N)); } } // This code is contributed by avijitmondal1998.
Javascript
<script> // JavaScript program for the above approach // Function to calculate count of 'N' digit // numbers such that bitwise AND of adjacent // digits is 0. function countOfNumbers(digit, prev, n) { // If digit = n + 1, a valid // n-digit number has been formed if (digit == n + 1) { return 1; } // If the state has // already been computed let val = dp[digit][prev]; 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 (digit == 1) { for (let i = (n == 1 ? 0 : 1); i <= 9; ++i) { val += countOfNumbers(digit + 1, i, n); } } // For remaining positions, // any digit from [0-9] can be placed // after checking the conditions. else { for (let i = 0; i <= 9; ++i) { // Check if bitwise AND // of current digit and // previous digit is 0. if ((i & prev) == 0) { val += countOfNumbers(digit + 1, i, n); } } } // Return answer return val; } // Initialize dp array with -1. let dp = Array(100).fill().map(() => Array(10).fill(-1)); // Given Input let N = 3; // Function call document.write(countOfNumbers(1, 0, N) + "<br>"); // This code is contributed by Potta Lokesh </script>
264
Complejidad temporal: O(N × 10 2 )
Espacio auxiliar: O(N × 10)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA