Conteo de números en Array que terminan con dígitos del número N

Dado un número N y una array arr[] que consiste en K números, la tarea es encontrar el conteo de números en la array que termina con cualquiera de los dígitos presentes en el número N. 

Ejemplos:  

Entrada: N = 1731 arr[] = {57, 6786} 
Salida: 1 
Explicación: 
Para 57, el último dígito es 7 y como 7 está presente es N, entonces el conteo es 1. 
Para 6786, el último dígito es 6 y dado que 6 no está presente en N, el conteo sigue siendo 1.
Entrada: N = 1324, arr[] = {23, 25, 12, 121} 
Salida: 3  

Enfoque ingenuo: el enfoque ingenuo para este problema es que para cada número en la array arr[] , verifique si su último dígito es igual a cualquiera de los dígitos en N. Incremente el conteo para cada número e imprímalo al final .
Complejidad de tiempo: O(N * K) , donde N es el número y K es el número de elementos en la array arr[]. 
Enfoque eficiente: el enfoque eficiente para este problema es realizar un preprocesamiento. 
 

• Inicialmente, cree una array A[] de tamaño 10.
• Esta array actúa como un hash que almacena todos los dígitos ocurridos en el número N.
• Después de esto, para cada número en la array arr[], extraiga el último dígito y verifique si este último dígito se encuentra o no en la array.
• Incremente el conteo para cada uno de dichos números e imprímalo al final. 
   

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

// C++ program to find the count
// of numbers in Array ending
// with digits of number N
 
#include <bits/stdc++.h>
using namespace std;
 
// Array to keep the
// track of digits occurred
// Initially all are 0(false)
int digit[10] = { 0 };
 
// Function to initialize true
// if the digit is present
void digitsPresent(int n)
{
    // Variable to store the last digit
    int lastDigit;
 
    // Loop to iterate through every
    // digit of the number N
    while (n != 0) {
        lastDigit = n % 10;
 
        // Updating the array according
        // to the presence of the
        // digit in n at the array index
        digit[lastDigit] = true;
        n /= 10;
    }
}
 
// Function to check if the
// numbers in the array
// end with the digits of
// the number N
int checkLastDigit(int num)
{
 
    // Variable to store the count
    int count = 0;
 
    // Variable to store the last digit
    int lastDigit;
    lastDigit = num % 10;
 
    // Checking the presence of
    // the last digit in N
    if (digit[lastDigit] == true)
        count++;
 
    return count;
}
 
// Function to find
// the required count
void findCount(int N, int K, int arr[])
{
 
    int count = 0;
 
    for (int i = 0; i < K; i++) {
 
        count = checkLastDigit(arr[i]) == 1
                    ? count + 1
                    : count;
    }
    cout << count << endl;
}
 
// Driver code
int main()
{
    int N = 1731;
 
    // Preprocessing
    digitsPresent(N);
 
    int K = 5;
    int arr[] = { 57, 6786,
                  1111, 3, 9812 };
 
    findCount(N, K, arr);
    return 0;
}

// Java program to find the count
// of numbers in Array ending
// with digits of number N
class GFG{
 
// Array to keep the
// track of digits occurred
// Initially all are 0(false)
public static int[] digit = new int[10];
 
// Function to initialize 1(true)
// if the digit is present
public static void digitsPresent(int n)
{
     
    // Variable to store the last digit
    int lastDigit;
 
    // Loop to iterate through every
    // digit of the number N
    while (n != 0)
    {
        lastDigit = n % 10;
 
        // Updating the array according
        // to the presence of the
        // digit in n at the array index
        digit[lastDigit] = 1;
        n /= 10;
    }
}
 
// Function to check if the
// numbers in the array
// end with the digits of
// the number N
public static int checkLastDigit(int num)
{
 
    // Variable to store the count
    int count = 0;
 
    // Variable to store the last digit
    int lastDigit;
    lastDigit = num % 10;
 
    // Checking the presence of
    // the last digit in N
    if (digit[lastDigit] == 1)
        count++;
 
    return count;
}
 
// Function to find
// the required count
public static void findCount(int N, int K,
                             int arr[])
{
    int count = 0;
 
    for(int i = 0; i < K; i++)
    {
       count = checkLastDigit(arr[i]) == 1 ?
               count + 1 : count;
    }
    System.out.println(count);
}
 
// Driver code
public static void main(String[] args)
{
    int N = 1731;
 
    // Preprocessing
    digitsPresent(N);
 
    int K = 5;
    int arr[] = { 57, 6786, 1111, 3, 9812 };
 
    findCount(N, K, arr);
}
}
 
// This code is contributed by Sayantan Pal

# Python3 program to find the count
# of numbers in Array ending
# with digits of number N
 
# Array to keep the
# track of digits occurred
# Initially all are 0(false)
digit = [0] * 10
 
# Function to initialize true
# if the digit is present
def digitsPresent(n):
     
    # Variable to store the last digit
    lastDigit = 0;
 
    # Loop to iterate through every
    # digit of the number N
    while (n != 0):
        lastDigit = n % 10;
         
        # Updating the array according
        # to the presence of the
        # digit in n at the array index
        digit[int(lastDigit)] = 1;
        n /= 10;
 
# Function to check if the numbers
# in the array end with the digits
# of the number N
def checkLastDigit(num):
 
    # Variable to store the count
    count = 0;
 
    # Variable to store the last digit
    lastDigit = 0;
    lastDigit = num % 10;
 
    # Checking the presence of
    # the last digit in N
    if (digit[int(lastDigit)] == 1):
        count += 1
 
    return count;
 
# Function to find the required count
def findCount(N, K, arr):
 
    count = 0;
    for i in range(K):
        if checkLastDigit(arr[i]) == 1:
            count += 1
        else:
            count
             
    print(count)
 
# Driver code
N = 1731;
 
# Preprocessing
digitsPresent(N);
 
K = 5;
arr = [ 57, 6786, 1111, 3, 9812 ];
 
findCount(N, K, arr);
 
# This code is contributed by grand_master

// C# program to find the count
// of numbers in Array ending
// with digits of number N
using System;
 
class GFG{
 
// Array to keep the track of digits occurred
// Initially all are 0(false)
public static int []digit = new int[10];
 
// Function to initialize 1(true)
// if the digit is present
public static void digitsPresent(int n)
{
 
    // Variable to store the last digit
    int lastDigit;
 
    // Loop to iterate through every
    // digit of the number N
    while (n != 0)
    {
        lastDigit = n % 10;
 
        // Updating the array according to the
        // presence of the digit in n at the
        // array index
        digit[lastDigit] = 1;
        n /= 10;
    }
}
 
// Function to check if the numbers in the
// array end with the digits of the number N
public static int checkLastDigit(int num)
{
 
    // Variable to store the count
    int count = 0;
 
    // Variable to store the last digit
    int lastDigit;
    lastDigit = num % 10;
 
    // Checking the presence of
    // the last digit in N
    if (digit[lastDigit] == 1)
        count++;
 
    return count;
}
 
// Function to find the required count
public static void findCount(int N, int K,
                             int []arr)
{
    int count = 0;
 
    for(int i = 0; i < K; i++)
    {
        count = checkLastDigit(arr[i]) == 1 ?
                count + 1 : count;
    }
    Console.WriteLine(count);
}
 
// Driver code
static public void Main()
{
    int N = 1731;
 
    // Preprocessing
    digitsPresent(N);
 
    int K = 5;
    int []arr = { 57, 6786, 1111, 3, 9812 };
 
    findCount(N, K, arr);
}
}
 
// This code is contributed by piyush3010

<script>
 
// Javascript program to find the count
// of numbers in Array ending
// with digits of number N
 
 
// Array to keep the
// track of digits occurred
// Initially all are 0(false)
let digit = new Uint8Array(10);
 
// Function to initialize true
// if the digit is present
function digitsPresent(n)
{
    // Variable to store the last digit
    let lastDigit;
 
    // Loop to iterate through every
    // digit of the number N
    while (n != 0) {
        lastDigit = n % 10;
 
        // Updating the array according
        // to the presence of the
        // digit in n at the array index
        digit[lastDigit] = true;
        n = Math.floor(n/10);
    }
}
 
// Function to check if the
// numbers in the array
// end with the digits of
// the number N
function checkLastDigit(num)
{
 
    // Variable to store the count
    let count = 0;
 
    // Variable to store the last digit
    let lastDigit;
    lastDigit = num % 10;
 
    // Checking the presence of
    // the last digit in N
    if (digit[lastDigit] == true)
        count++;
 
    return count;
}
 
// Function to find
// the required count
function findCount(N, K, arr)
{
    let count = 0;
 
    for (let i = 0; i < K; i++) {
 
        count = checkLastDigit(arr[i]) == 1
                    ? count + 1
                    : count;
    }
    document.write(count + "<br>");
}
 
// Driver code
 
    let N = 1731;
 
    // Preprocessing
    digitsPresent(N);
 
    let K = 5;
    let arr = [ 57, 6786,
                1111, 3, 9812 ];
 
    findCount(N, K, arr);
 
//This code is contributed by Mayank Tyagi
</script>

3

Complejidad del tiempo:

• O(N), donde N es el número dado para el preprocesamiento.
• O(K), donde K es el número de consultas para encontrar respuestas a las consultas.