Recuento de números de N dígitos con al menos un dígito como K

Dado un número N y un dígito K , la tarea es contar números de N dígitos con al menos un dígito como K.

Ejemplos:

Entrada: N= 3, K = 2
Salida: 252
Explicación: 
Para una ocurrencia de 2 – 
En un número de longitud 3, son posibles los siguientes casos:
=>Cuando el primer dígito es 2 y los otros dos dígitos pueden tener 9 valores excepto ‘ 2’. 
Por lo tanto, 9*9 = 81 combinaciones son posibles.
=> Cuando el segundo dígito es 2 y el primer dígito puede tener 8 valores del 1 al 9 excepto ‘2’ 
y el tercer dígito puede tener 9 valores del 0 al 9 excepto ‘2’.
Así 8*9 = 72 combinación válida.
=>Cuando el tercer dígito es 2, el primer dígito puede tener 8 valores del 1 al 9 excepto ‘2’ 
y el segundo dígito puede tener 9 valores del 0 al 9 excepto ‘2’, por lo tanto, 8*9 = 72. 
Por lo tanto, la combinación válida total con una aparición de 2 = 72 + 72 + 81 = 225.
Para dos ocurrencias de 2: 
el primer y segundo dígito pueden ser 2 y el tercer dígito puede tener 9 valores de 0 a 9. El 
segundo y tercer dígito pueden tener un valor de 2 y el primer dígito 
puede tener 8 valores de 1 a 9 excepto 2. 
Primero y tercero el dígito puede tener valores 2 y el segundo dígito 
puede tener 9 valores de 0 a 9 excepto 2. 
Por lo tanto, la combinación válida total con dos ocurrencias de 2 = 9 + 8 + 9 = 26.
Para que los tres dígitos sean 2, 
solo puede haber 1 combinación.
Por lo tanto, el total de números posibles con al menos una ocurrencia de 2 = 225 + 26 + 1 = 252.

Entrada: N = 9, K = 8
Salida: 555626232

Planteamiento: El problema se puede resolver con base en la siguiente idea matemática:

Encuentre la diferencia entre el conteo de números de N dígitos únicos posibles y el conteo de todos los números de N dígitos únicos sin ocurrencia del dígito K.

Siga los pasos mencionados a continuación para implementar esta idea: 

• Encuentre el conteo de todos los números de N dígitos = 9 x 10 ^N-1 , el lugar más a la izquierda puede ser cualquier dígito del 1 al 9, otros dígitos pueden tener cualquier valor entre 0 y 9.
• Encuentre el recuento de todos los números de N dígitos sin que aparezca K = 8 x 9 ^n-1 , el lugar más a la izquierda puede ser cualquier dígito del 1 al 9 excepto K y   otros dígitos pueden tener cualquier valor entre 0 y 9 excepto K.
• Recuento total de números de N dígitos con al menos una ocurrencia de K 
  = Recuento de todos los números de N dígitos – Recuento de todos los números de N dígitos sin ocurrencia de K.

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

// C++ Code to Implement the approach
// Function to find the total possible numbers
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the total possible numbers
void required_numbers(int n, int k)
{
    int t, h, r;
   
    // Find all n digits numbers
    t = 9 * pow (10, (n - 1));
   
    // Find n digits number in which no k occurs
    h = 8 * pow (9, (n - 1));
   
    // Calculate the required value as
    // the difference of the above two values
    r = t - h;
    cout << r;
}
 
// Driver code
int main()
{
 
    int N, K;
    N = 3;
    K = 2;
   
    // Function call
    required_numbers(N, K);
    return 0;
}
 
// This code is contributed by ANKITKUMAR34.

// Java Code to implement the approach
// Function to find the total possible numbers
import java.io.*;
import java.util.*;
 
class GFG {
    // Function to find the total possible numbers
    public static void required_numbers(int n, int k)
    {
        // Find all n digits numbers
        int t = 9 * (int)Math.pow(10, (n - 1));
 
        // Find n digits number in which no k occurs
        int h = 8 * (int)Math.pow(9, (n - 1));
 
        // Calculate the required value as
        // the difference of the above two values
        int r = t - h;
        System.out.print(r);
    }
    public static void main(String[] args)
    {
        int N = 3;
        int K = 2;
 
        // Function call
        required_numbers(N, K);
    }
}
 
// This code is contributed by Rohit Pradhan

# Python Code to Implement the approach
 
 
# Function to find the total possible numbers
def required_numbers(n, k):
 
    # Find all n digits numbers
    t = 9 * 10 ** (n - 1)
 
    # Find n digits number in which no k occurs
    h = 8 * 9 ** (n - 1)
 
    # Calculate the required value as
    # the difference of the above two values
    r = t - h
    return(r)
 
 
# Driver code
if __name__ == '__main__':
    N = 3
    K = 2
 
    # Function call
    print(required_numbers(N, K))

// C# Code to implement the approach
// Function to find the total possible numbers
 
using System;
 
public class GFG {
     
    // Function to find the total possible numbers
    public static void required_numbers(int n, int k)
    {
        // Find all n digits numbers
        int t = 9 * (int)Math.Pow(10, (n - 1));
 
        // Find n digits number in which no k occurs
        int h = 8 * (int)Math.Pow(9, (n - 1));
 
        // Calculate the required value as
        // the difference of the above two values
        int r = t - h;
         
        Console.WriteLine(r);
    }
     
    public static void Main(string[] args)
    {
        int N = 3;
        int K = 2;
 
        // Function call
        required_numbers(N, K);
    }
}
 
// This code is contributed by AnkThon

252

Complejidad Temporal: O(1).
Espacio Auxiliar: O(1).