Given an array arr[] consisting of N positive integers and a positive integer K, the task is to find the count of array elements whose distinct digits are a subset of the digits of K.
Examples:
Input: arr[] = { 1, 12, 1222, 13, 2 }, K = 12
Output: 4
Explanation:
Distinct Digits of K are { 1, 2 }
Distinct Digits of arr[0] are { 1 }, which is the subset of the digits of K.
Distinct Digits of arr[1] are { 1, 2 }, which is the subset of the digits of K.
Distinct Digits of arr[2] are { 1, 2 }, which is the subset of the digits of K.
Distinct Digits of arr[3] are { 1, 3 }, which is not the subset of the digits of K.
Distinct Digits of arr[4] are { 2 }, which is the subset of the digits of K.
Therefore, the required output is 4.Input: arr = {1, 2, 3, 4, 1234}, K = 1234
Output: 5
Naive Approach: The simplest approach to solve the problem is to traverse the array arr[] and for each array element, check if all its distinct digits appear in K or not. If found to be true, then increment the count. Finally, print the count obtained.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check a digit occurs// in the digit of K or notstatic bool isValidDigit(int digit, int K){ // Iterate over all possible // digits of K while (K != 0) { // If current digit // equal to digit if (K % 10 == digit) { return true; } // Update K K = K / 10; } return false;}// Function to find the count of array // elements whose distinct digits are // a subset of digits of Kint noOfValidNumbers(int K, int arr[], int n){ // Stores count of array elements // whose distinct digits are subset // of digits of K int count = 0; // Traverse the array, []arr for(int i = 0; i < n; i++) { // Stores the current element int no = arr[i]; // Check if all the digits arr[i] // is a subset of the digits of // K or not bool flag = true; // Iterate over all possible // digits of arr[i] while (no != 0) { // Stores current digit int digit = no % 10; // If current digit does not // appear in K if (!isValidDigit(digit, K)) { // Update flag flag = false; break; } // Update no no = no / 10; } // If all the digits arr[i] // appear in K if (flag == true) { // Update count count++; } } // Finally print count return count;}// Driver Codeint main(){ int K = 12; int arr[] = { 1, 12, 1222, 13, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << noOfValidNumbers(K, arr, n); return 0;}// This code is contributed by susmitakundugoaldanga |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to check a digit occurs // in the digit of K or not static boolean isValidDigit(int digit, int K) { // Iterate over all possible // digits of K while (K != 0) { // If current digit // equal to digit if (K % 10 == digit) { return true; } // Update K K = K / 10; } return false; } // Function to find the count of array elements // whose distinct digits are a subset of digits of K static int noOfValidNumbers(int K, int arr[]) { // Stores count of array elements // whose distinct digits are subset // of digits of K int count = 0; // Traverse the array, arr[] for (int i = 0; i < arr.length; i++) { // Stores the current element int no = arr[i]; // Check if all the digits arr[i] // is a subset of the digits of // K or not boolean flag = true; // Iterate over all possible // digits of arr[i] while (no != 0) { // Stores current digit int digit = no % 10; // If current digit does not // appear in K if (!isValidDigit(digit, K)) { // Update flag flag = false; break; } // Update no no = no / 10; } // If all the digits arr[i] appear in K if (flag == true) { // Update count count++; } } // Finally print count return count; } // Driver Code public static void main(String[] args) { int K = 12; int arr[] = { 1, 12, 1222, 13, 2 }; System.out.println(noOfValidNumbers(K, arr)); }} |
Python3
# Python3 program for the above approach# Function to check a digit occurs# in the digit of K or notdef isValidDigit(digit, K): # Iterate over all possible # digits of K while (K != 0): # If current digit # equal to digit if (K % 10 == digit): return True # Update K K = K // 10 return False# Function to find the count of array# elements whose distinct digits are# a subset of digits of Kdef noOfValidNumbers(K, arr, n): # Stores count of array elements # whose distinct digits are subset # of digits of K count = 0 # Traverse the array, []arr for i in range(n): # Stores the current element no = arr[i] # Check if all the digits arr[i] # is a subset of the digits of # K or not flag = True # Iterate over all possible # digits of arr[i] while (no != 0): # Stores current digit digit = no % 10 # If current digit does not # appear in K if (not isValidDigit(digit, K)): # Update flag flag = False break # Update no no = no // 10 # If all the digits arr[i] # appear in K if (flag == True): # Update count count += 1 # Finally print count return count# Driver Codeif __name__ == "__main__": K = 12 arr = [1, 12, 1222, 13, 2] n = len(arr) print(noOfValidNumbers(K, arr, n)) # This code is contributed by chitranayal. |
C#
// C# program for the above approachusing System;class GFG{// Function to check a digit occurs// in the digit of K or notstatic bool isValidDigit(int digit, int K){ // Iterate over all possible // digits of K while (K != 0) { // If current digit // equal to digit if (K % 10 == digit) { return true; } // Update K K = K / 10; } return false;}// Function to find the count of array elements// whose distinct digits are a subset of digits of Kstatic int noOfValidNumbers(int K, int []arr){ // Stores count of array elements // whose distinct digits are subset // of digits of K int count = 0; // Traverse the array, []arr for(int i = 0; i < arr.Length; i++) { // Stores the current element int no = arr[i]; // Check if all the digits arr[i] // is a subset of the digits of // K or not bool flag = true; // Iterate over all possible // digits of arr[i] while (no != 0) { // Stores current digit int digit = no % 10; // If current digit does not // appear in K if (!isValidDigit(digit, K)) { // Update flag flag = false; break; } // Update no no = no / 10; } // If all the digits arr[i] appear in K if (flag == true) { // Update count count++; } } // Finally print count return count;}// Driver Codepublic static void Main(String[] args){ int K = 12; int []arr = { 1, 12, 1222, 13, 2 }; Console.WriteLine(noOfValidNumbers(K, arr));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to check a digit occurs// in the digit of K or notfunction isValidDigit(digit, K){ // Iterate over all possible // digits of K while (K != 0) { // If current digit // equal to digit if (K % 10 == digit) { return true; } // Update K K = parseInt(K / 10); } return false;}// Function to find the count of array // elements whose distinct digits are // a subset of digits of Kfunction noOfValidNumbers(K, arr, n){ // Stores count of array elements // whose distinct digits are subset // of digits of K let count = 0; // Traverse the array, []arr for(let i = 0; i < n; i++) { // Stores the current element let no = arr[i]; // Check if all the digits arr[i] // is a subset of the digits of // K or not let flag = true; // Iterate over all possible // digits of arr[i] while (no != 0) { // Stores current digit let digit = no % 10; // If current digit does not // appear in K if (!isValidDigit(digit, K)) { // Update flag flag = false; break; } // Update no no = parseInt(no / 10); } // If all the digits arr[i] // appear in K if (flag == true) { // Update count count++; } } // Finally print count return count;}// Driver Code let K = 12; let arr = [ 1, 12, 1222, 13, 2 ]; let n = arr.length; document.write(noOfValidNumbers(K, arr, n)); </script> |
Output:
4
Time Complexity: O(N * log10(K) * log10(Max)), Max is the largest array element
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using a HashSet. Follow the steps below to solve the problem:
- Iterate over the digits of K and insert all the digits into a HashSet say set
- Traverse the array arr[] and for every array element, iterate over all the digits of the current element and check if all the digits are present in the set or not. If found to be true, then increment the count.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to the count of array elements whose// distinct digits are a subset of the digits of Kstatic int noOfValidKbers(int K, vector<int> arr){ // Stores distinct digits of K map<int,int> set; // Iterate over all the digits of K while (K != 0) { // Insert current digit into set set[K % 10] = 1; // Update K K = K / 10; } // Stores the count of array elements // whose distinct digits are a subset // of the digits of K int count = 0; // Traverse the array, arr[] for (int i = 0; i < arr.size(); i++) { // Stores current element int no = arr[i]; // Check if all the digits of arr[i] // are present in K or not bool flag = true; // Iterate over all the digits of arr[i] while (no != 0) { // Stores current digit int digit = no % 10; // If digit not present in the set if (set.find(digit)==set.end()) { // Update flag flag = false; break; } // Update no no = no / 10; } // If all the digits of // arr[i] present in set if (flag == true) { // Update count count++; } } return count;}// Driver Codeint main(){ int K = 12; vector<int> arr = { 1, 12, 1222, 13, 2 }; cout<<(noOfValidKbers(K, arr));}// This code is contributed by mohit kumar 29 |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to the count of array elements whose // distinct digits are a subset of the digits of K static int noOfValidKbers(int K, int arr[]) { // Stores distinct digits of K HashSet<Integer> set = new HashSet<>(); // Iterate over all the digits of K while (K != 0) { // Insert current digit into set set.add(K % 10); // Update K K = K / 10; } // Stores the count of array elements // whose distinct digits are a subset // of the digits of K int count = 0; // Traverse the array, arr[] for (int i = 0; i < arr.length; i++) { // Stores current element int no = arr[i]; // Check if all the digits of arr[i] // are present in K or not boolean flag = true; // Iterate over all the digits of arr[i] while (no != 0) { // Stores current digit int digit = no % 10; // If digit not present in the set if (!set.contains(digit)) { // Update flag flag = false; break; } // Update no no = no / 10; } // If all the digits of // arr[i] present in set if (flag == true) { // Update count count++; } } return count; } // Driver Code public static void main(String[] args) { int K = 12; int arr[] = { 1, 12, 1222, 13, 2 }; System.out.println(noOfValidKbers(K, arr)); }} |
Python3
# Python 3 program to implement# the above approach# Function to the count of array elements whose# distinct digits are a subst of the digits of Kdef noOfValidKbers(K, arr): # Stores distinct digits of K st = {} # Iterate over all the digits of K while(K != 0): # Insert current digit into st if(K % 10 in st): st[K % 10] = 1 else: st[K % 10] = st.get(K % 10, 0) + 1 # Update K K = K // 10 # Stores the count of array elements # whose distinct digits are a subst # of the digits of K count = 0 # Traverse the array, arr[] for i in range(len(arr)): # Stores current element no = arr[i] # Check if all the digits of arr[i] # are present in K or not flag = True # Iterate over all the digits of arr[i] while(no != 0): # Stores current digit digit = no % 10 # If digit not present in the st if (digit not in st): # Update flag flag = False break # Update no no = no//10 # If all the digits of # arr[i] present in st if (flag == True): # Update count count += 1 return count# Driver Codeif __name__ == '__main__': K = 12 arr = [1, 12, 1222, 13, 2] print(noOfValidKbers(K, arr)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to the count of array elements whose// distinct digits are a subset of the digits of Kstatic int noOfValidKbers(int K, int []arr){ // Stores distinct digits of K HashSet<int> set = new HashSet<int>(); // Iterate over all the digits of K while (K != 0) { // Insert current digit into set set.Add(K % 10); // Update K K = K / 10; } // Stores the count of array elements // whose distinct digits are a subset // of the digits of K int count = 0; // Traverse the array, []arr for(int i = 0; i < arr.Length; i++) { // Stores current element int no = arr[i]; // Check if all the digits of arr[i] // are present in K or not bool flag = true; // Iterate over all the digits of arr[i] while (no != 0) { // Stores current digit int digit = no % 10; // If digit not present in the set if (!set.Contains(digit)) { // Update flag flag = false; break; } // Update no no = no / 10; } // If all the digits of // arr[i] present in set if (flag == true) { // Update count count++; } } return count;}// Driver Codepublic static void Main(String[] args){ int K = 12; int []arr = { 1, 12, 1222, 13, 2 }; Console.WriteLine(noOfValidKbers(K, arr));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach // Function to the count of array elements whose // distinct digits are a subset of the digits of K function noOfValidKbers(K , arr) { // Stores distinct digits of K var set = new Set(); // Iterate over all the digits of K while (K != 0) { // Insert current digit into set set.add(K % 10); // Update K K = parseInt(K / 10); } // Stores the count of array elements // whose distinct digits are a subset // of the digits of K var count = 0; // Traverse the array, arr for (i = 0; i < arr.length; i++) { // Stores current element var no = arr[i]; // Check if all the digits of arr[i] // are present in K or not var flag = true; // Iterate over all the digits of arr[i] while (no != 0) { // Stores current digit var digit = no % 10; // If digit not present in the set if (!set.has(digit)) { // Update flag flag = false; break; } // Update no no = parseInt(no / 10); } // If all the digits of // arr[i] present in set if (flag == true) { // Update count count++; } } return count; } // Driver Code var K = 12; var arr = [ 1, 12, 1222, 13, 2 ]; document.write(noOfValidKbers(K, arr));// This code contributed by umadevi9616</script> |
Output:
4
Time Complexity: O(N * log10(Max)), where Max is the largest array element
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!
