Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es encontrar el recuento de elementos de la array cuyos dígitos distintos son un subconjunto de los dígitos de K .
Ejemplos:
Entrada: arr[] = { 1, 12, 1222, 13, 2 }, K = 12
Salida: 4
Explicación:
Los dígitos distintos de K son { 1, 2 }
Los dígitos distintos de arr[0] son { 1 }, que es el subconjunto de los dígitos de K.
Los dígitos distintos de arr[1] son { 1, 2 }, que es el subconjunto de los dígitos de K.
Los dígitos distintos de arr[2] son { 1, 2 }, que es el subconjunto de los dígitos de K.
Los dígitos distintos de arr[3] son { 1, 3 }, que no es el subconjunto de los dígitos de K.
Los dígitos distintos de arr[4] son { 2 }, que es el subconjunto de los dígitos de K.
Por lo tanto, la salida requerida es 4.Entrada : arr = {1, 2, 3, 4, 1234}, K = 1234
Salida: 5
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array arr[] y, para cada elemento de la array, verificar si todos sus dígitos distintos aparecen en K o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
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 not
static 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 K
int 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 Code
int 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 approach
import 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 not def 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 K def 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 Code if __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 approach
using System;
class GFG{
// Function to check a digit occurs
// in the digit of K or not
static 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 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
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 Code
public 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 not
function 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 K
function 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>
Producción:
4
Complejidad de tiempo: O (N * log 10 (K) * log 10 (Max)), Max es el elemento de array más grande
Espacio auxiliar: O (1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante un HashSet . Siga los pasos a continuación para resolver el problema:
- Iterar sobre los dígitos de K e insertar todos los dígitos en un HashSet , digamos conjunto
- Recorra la array arr[] y para cada elemento de la array, itere sobre todos los dígitos del elemento actual y verifique si todos los dígitos están presentes en el conjunto o no . Si se encuentra que es cierto, entonces incremente el conteo.
- Finalmente, imprima el conteo obtenido.
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 K
static 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 Code
int 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 approach
import 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 K
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
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<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 Code
public 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>
Producción:
4
Complejidad de tiempo: O(N * log 10 (Max)), donde Max es el elemento de array más grande
Espacio auxiliar: O(10)