Recuento de números de N dígitos en base K sin dos ceros consecutivos

Dados dos enteros N y K , la tarea es encontrar el conteo de todos los enteros en base K que cumplan las siguientes condiciones: 
 

1. Los números enteros deben tener exactamente N dígitos.
2. No debe haber ningún 0 inicial .
3. No debe haber ningún par de dígitos consecutivos tal que ambos dígitos sean 0 .

Ejemplos: 
 

Entrada: N = 3, K = 10 
Salida: 891 
Todos los números de 3 dígitos en base 10 pertenecen al rango [100, 999]. 
De estos números, solo 100, 200, 300, 400, …, 900 no son válidos. 
Por lo tanto, los enteros válidos son 900 – 9 = 891
Entrada: N = 2, K = 10 
Salida: 90 
 

Enfoque ingenuo: escriba una función count_numbers (int k, int n, bool flag) que devolverá el recuento de N números de dígitos posibles de base K y flag le dirá si el dígito elegido previamente era 0 o no. Llame a esta función recursivamente para count_numbers(int k, int n-1, bool flag), y usando la bandera, se puede evitar la aparición de dos 0 consecutivos.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
int count_numbers(int k, int n, bool flag)
{
 
    // Base case
    if (n == 1) {
 
        // If 0 wasn't chosen previously
        if (flag) {
            return (k - 1);
        }
        else {
            return 1;
        }
    }
 
    // If 0 wasn't chosen previously
    if (flag)
        return (k - 1) * (count_numbers(k, n - 1, 0)
                          + count_numbers(k, n - 1, 1));
    else
        return count_numbers(k, n - 1, 1);
}
 
// Driver code
int main()
{
    int n = 3;
    int k = 10;
    cout << count_numbers(k, n, true);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
static int count_numbers(int k, int n,
                         boolean flag)
{
 
    // Base case
    if (n == 1)
    {
 
        // If 0 wasn't chosen previously
        if (flag)
        {
            return (k - 1);
        }
        else
        {
            return 1;
        }
    }
 
    // If 0 wasn't chosen previously
    if (flag)
        return (k - 1) * (count_numbers(k, n - 1, false) +
                          count_numbers(k, n - 1, true));
    else
        return count_numbers(k, n - 1, true);
}
 
// Driver code
public static void main (String[] args)
{
    int n = 3;
    int k = 10;
    System.out.println(count_numbers(k, n, true));
}
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the count of
# n-digit numbers that satisfy
# the given conditions
def count_numbers(k, n, flag) :
 
    # Base case
    if (n == 1) :
 
        # If 0 wasn't chosen previously
        if (flag) :
            return (k - 1)
        else :
            return 1
 
    # If 0 wasn't chosen previously
    if (flag) :
        return (k - 1) * (count_numbers(k, n - 1, 0) +
                          count_numbers(k, n - 1, 1))
    else :
        return count_numbers(k, n - 1, 1)
 
# Driver code
n = 3
k = 10
print(count_numbers(k, n, True))
 
# This code is contributed by
# divyamohan123

// C# implementation of the approach
using System;
                     
class GFG
{
     
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
static int count_numbers(int k, int n,
                         bool flag)
{
 
    // Base case
    if (n == 1)
    {
 
        // If 0 wasn't chosen previously
        if (flag)
        {
            return (k - 1);
        }
        else
        {
            return 1;
        }
    }
 
    // If 0 wasn't chosen previously
    if (flag)
        return (k - 1) * (count_numbers(k, n - 1, false) +
                          count_numbers(k, n - 1, true));
    else
        return count_numbers(k, n - 1, true);
}
 
// Driver code
public static void Main (String[] args)
{
    int n = 3;
    int k = 10;
    Console.Write(count_numbers(k, n, true));
}
}
 
// This code is contributed by 29AjayKuma

<script>
// Javascript implementation of the approach
 
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
function count_numbers(k, n, flag)
{
 
    // Base case
    if (n == 1) {
 
        // If 0 wasn't chosen previously
        if (flag) {
            return (k - 1);
        }
        else {
            return 1;
        }
    }
 
    // If 0 wasn't chosen previously
    if (flag)
        return (k - 1) * (count_numbers(k, n - 1, 0)
                          + count_numbers(k, n - 1, 1));
    else
        return count_numbers(k, n - 1, 1);
}
 
// Driver code
    let n = 3;
    let k = 10;
    document.write(count_numbers(k, n, true));
 
// This code is contributed by souravmahato348.
</script>

891

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ² )

Enfoque eficiente: ahora que el problema se ha resuelto mediante recursividad, se puede usar un DP 2-D para resolver este problema dp[n + 1][2] donde dp[i][0] dará la cantidad de números de i dígitos posible que termine en 0 y dp[i][1] dará el número de números de i dígitos posibles que terminen en distinto de cero. 
La relación de recurrencia será: 
 

dp[i][0] = dp[i – 1][1]; 
dp[i][1] = (dp[i – 1][0] + dp[i – 1][1]) * (K – 1); 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
int count_numbers(int k, int n)
{
 
    // DP array to store the
    // pre-calculated states
    int dp[n + 1][2];
 
    // Base cases
    dp[1][0] = 0;
    dp[1][1] = k - 1;
    for (int i = 2; i <= n; i++) {
 
        // i-digit numbers ending with 0
        // can be formed by concatenating
        // 0 in the end of all the (i - 1)-digit
        // number ending at a non-zero digit
        dp[i][0] = dp[i - 1][1];
 
        // i-digit numbers ending with non-zero
        // can be formed by concatenating any non-zero
        // digit in the end of all the (i - 1)-digit
        // number ending with any digit
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1);
    }
 
    // n-digit number ending with
    // and ending with non-zero
    return dp[n][0] + dp[n][1];
}
 
// Driver code
int main()
{
    int k = 10;
    int n = 3;
    cout << count_numbers(k, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
static int count_numbers(int k, int n)
{
 
    // DP array to store the
    // pre-calculated states
    int [][]dp = new int[n + 1][2];
 
    // Base cases
    dp[1][0] = 0;
    dp[1][1] = k - 1;
    for (int i = 2; i <= n; i++)
    {
 
        // i-digit numbers ending with 0
        // can be formed by concatenating
        // 0 in the end of all the (i - 1)-digit
        // number ending at a non-zero digit
        dp[i][0] = dp[i - 1][1];
 
        // i-digit numbers ending with non-zero
        // can be formed by concatenating any non-zero
        // digit in the end of all the (i - 1)-digit
        // number ending with any digit
        dp[i][1] = (dp[i - 1][0] +
                    dp[i - 1][1]) * (k - 1);
    }
 
    // n-digit number ending with
    // and ending with non-zero
    return dp[n][0] + dp[n][1];
}
 
// Driver code
public static void main(String[] args)
{
    int k = 10;
    int n = 3;
    System.out.println(count_numbers(k, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the count of
# n-digit numbers that satisfy
# the given conditions
def count_numbers(k, n):
 
    # DP array to store the
    # pre-calculated states
    dp = [[0 for i in range(2)]
             for i in range(n + 1)]
 
    # Base cases
    dp[1][0] = 0
    dp[1][1] = k - 1
    for i in range(2, n + 1):
 
        # i-digit numbers ending with 0
        # can be formed by concatenating
        # 0 in the end of all the (i - 1)-digit
        # number ending at a non-zero digit
        dp[i][0] = dp[i - 1][1]
 
        # i-digit numbers ending with non-zero
        # can be formed by concatenating any non-zero
        # digit in the end of all the (i - 1)-digit
        # number ending with any digit
        dp[i][1] = (dp[i - 1][0] +
                    dp[i - 1][1]) * (k - 1)
 
    # n-digit number ending with
    # and ending with non-zero
    return dp[n][0] + dp[n][1]
 
# Driver code
k = 10
n = 3
print(count_numbers(k, n))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
                     
class GFG
{
 
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
static int count_numbers(int k, int n)
{
 
    // DP array to store the
    // pre-calculated states
    int [,]dp = new int[n + 1, 2];
 
    // Base cases
    dp[1, 0] = 0;
    dp[1, 1] = k - 1;
    for (int i = 2; i <= n; i++)
    {
 
        // i-digit numbers ending with 0
        // can be formed by concatenating
        // 0 in the end of all the (i - 1)-digit
        // number ending at a non-zero digit
        dp[i, 0] = dp[i - 1, 1];
 
        // i-digit numbers ending with non-zero
        // can be formed by concatenating any non-zero
        // digit in the end of all the (i - 1)-digit
        // number ending with any digit
        dp[i, 1] = (dp[i - 1, 0] +
                    dp[i - 1, 1]) * (k - 1);
    }
 
    // n-digit number ending with
    // and ending with non-zero
    return dp[n, 0] + dp[n, 1];
}
 
// Driver code
public static void Main(String[] args)
{
    int k = 10;
    int n = 3;
    Console.WriteLine(count_numbers(k, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of
// n-digit numbers that satisfy
// the given conditions
function count_numbers(k, n)
{
 
    // DP array to store the
    // pre-calculated states
    let dp = new Array(n + 1);
    for (let i = 0; i < n + 1; i++)
        dp[i] = new Array(2);
 
    // Base cases
    dp[1][0] = 0;
    dp[1][1] = k - 1;
    for (let i = 2; i <= n; i++) {
 
        // i-digit numbers ending with 0
        // can be formed by concatenating
        // 0 in the end of all the (i - 1)-digit
        // number ending at a non-zero digit
        dp[i][0] = dp[i - 1][1];
 
        // i-digit numbers ending with non-zero
        // can be formed by concatenating any non-zero
        // digit in the end of all the (i - 1)-digit
        // number ending with any digit
        dp[i][1] = (dp[i - 1][0] +
                    dp[i - 1][1]) * (k - 1);
    }
 
    // n-digit number ending with
    // and ending with non-zero
    return dp[n][0] + dp[n][1];
}
 
// Driver code
    let k = 10;
    let n = 3;
    document.write(count_numbers(k, n));
 
</script>

891