Recuento de números de N dígitos cuyo AND bit a bit de dígitos adyacentes es igual a 0

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++ 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 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 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# 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.

<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 ² )
Espacio auxiliar: O(N × 10)