Given a number N and an array arr[] consisting of K numbers, the task is to find the count of numbers in the array which ends with any of the digit present in the number N.
Examples:
Input: N = 1731 arr[] = {57, 6786}
Output: 1
Explanation:
For 57, the last digit is 7 and since 7 is present is N, so the count is 1.
For 6786, the last digit is 6 and since 6 is not present in N, the count remains 1.Input: N = 1324, arr[] = {23, 25, 12, 121}
Output: 3
Naive Approach: The naive approach for this problem is that for every number in the array arr[], check if its last digit is equal to any of the digits in N. Increment the count for each of such number and print it at the end.
Time Complexity: O(N * K), where N is the number and K is the number of elements in the array arr[].
Efficient Approach: The efficient approach for this problem is to perform a preprocessing.
- Initially, create an array A[] of size 10.
- This array acts as a hash which stores all the digits occurred in the number N.
- After this, for every number in the array arr[], extract the last digit and check if this last digit has occurred or not in the array.
- Increment the count for each of such number and print it at the end.
Below is the implementation of the above approach:
C++
// 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 presentvoid 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 Nint 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 countvoid 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 codeint main(){ int N = 1731; // Preprocessing digitsPresent(N); int K = 5; int arr[] = { 57, 6786, 1111, 3, 9812 }; findCount(N, K, arr); return 0;} |
Java
// Java program to find the count// of numbers in Array ending// with digits of number Nimport java.io.*;public 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 presentpublic 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 Npublic 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 countpublic 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 codepublic 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
# 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 presentdef 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 Ndef 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 countdef findCount(N, K, arr): count = 0; for i in range(K): if checkLastDigit(arr[i]) == 1: count += 1 else: count print(count)# Driver codeN = 1731;# PreprocessingdigitsPresent(N);K = 5;arr = [ 57, 6786, 1111, 3, 9812 ];findCount(N, K, arr);# This code is contributed by grand_master |
C#
// C# program to find the count// of numbers in Array ending// with digits of number Nusing 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 presentpublic 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 Npublic 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 countpublic 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 codestatic 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 |
Javascript
<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 presentfunction 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 Nfunction 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 countfunction 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> |
Output:
3
Time Complexity:
- O(N), where N is the given number for preprocessing.
- O(K), where K is the number of queries to find answers for the queries.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
