Subsecuencia más larga con al menos un dígito común en cada elemento

Dada una array. La tarea es encontrar la longitud de la subsecuencia más larga en la que todos los elementos deben tener al menos un dígito en común.

Ejemplos: 

Entrada : arr[] = { 11, 12, 23, 74, 13 } 
Salida : 3 
Explicación : Los elementos 11, 12 y 13 tienen el dígito ‘1’ como común. Por lo tanto, es la subsecuencia más larga requerida.
Entrada : arr[] = { 12, 90, 67, 78, 45 } 
Salida : 2 
 

Enfoque normal: encuentre todas las subsecuencias de la array y encuentre la subsecuencia en la que cada elemento debe tener un dígito común. Luego tenemos que encontrar la subsecuencia más larga e imprimir la longitud de esa subsecuencia. Este método tendrá una complejidad de tiempo exponencial.

Enfoque eficiente: la idea es tomar una array hash de tamaño 10 para almacenar el recuento de dígitos del 0 al 9 que aparecen en los elementos de la array. Recorra la array y para cada elemento de la array, encuentre los dígitos únicos en ese elemento e incremente su conteo en la array hash. Ahora, el dígito con el conteo máximo en la array hash indica que es el dígito común máximo que ocurre entre los elementos de la array. Entonces, la longitud de la subsecuencia más larga requerida será el conteo máximo en la array hash.

Tomemos un ejemplo, 
 

Deje que la array sea arr[] = {11, 12, 13, 24} 
Inicialmente, la array de recuento es { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } El
primer elemento es 11, por lo que los dígitos son 1 y 1 (pero 1 se contará una vez) la 
array de conteo es { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 } El
segundo elemento es 12, por lo que los dígitos son 1, 2 
la array de conteo es { 0 , 2, 1, 0, 0, 0, 0, 0, 0, 0 } El
tercer elemento es 13 por lo que los dígitos son 1, 
la array de conteo 3 es { 0, 3, 1, 1, 0, 0, 0, 0, 0 , 0 }
El cuarto elemento es 24, por lo que los dígitos son 2,  la
array de conteo 4 es { 0, 3, 2, 1, 1, 0, 0, 0, 0, 0 }
Entonces, el valor máximo en la array de conteo es 3 
Por lo tanto, 3 ser la respuesta 
 

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

// C++ program to find the length of subsequence which has
// atleast one digit common among all its elements
#include <bits/stdc++.h>
using namespace std;
 
// If the number contains a digit increase
// the count by 1 (even if it has multiple
// same digit the count should be increased
// by only once)
void count_(int count[], int e)
{
    // Hash to make it sure that a digit
    // is counted only once
    bool hash[10];
 
    // Set the hash to its initial value
    memset(hash, false, sizeof(hash));
 
    // Extract the digits
    while (e > 0) {
 
        // If the digit did not appear before
        if (hash[e % 10] == false)
 
            // Increase the count
            count[e % 10]++;
 
        // Mark the digit as visited
        hash[e % 10] = true;
 
        // Delete the digit
        e /= 10;
    }
}
 
// Function to find the length of subsequence which has
// atleast one digit common among all its elements
void find_subsequence(int arr[], int n)
{
    // Count of digits
    int count[10];
 
    // Set the initial value to zero
    memset(count, 0, sizeof(count));
    for (int i = 0; i < n; i++) {
 
        // Extract the digits of the element
        // and increase the count
        count_(count, arr[i]);
    }
 
    // Longest subsequence
    int longest = 0;
 
    // Get the longest subsequence
    for (int i = 0; i < 10; i++)
        longest = max(count[i], longest);
 
    // Print the length of longest subsequence
    cout << longest << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 11, 12, 23, 74, 13 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    find_subsequence(arr, n);
 
    return 0;
}

// Java program to find the length of subsequence which has
// atleast one digit common among all its elements
 
import java.io.*;
 
class GFG {
 
// If the number contains a digit increase
// the count by 1 (even if it has multiple
// same digit the count should be increased
// by only once)
static void count_(int count[], int e)
{
    // Hash to make it sure that a digit
    // is counted only once
    boolean hash[] = new boolean[10];
 
    // Set the hash to its initial value
    //memset(hash, false, sizeof(hash));
 
    // Extract the digits
    while (e > 0) {
 
        // If the digit did not appear before
        if (hash[e % 10] == false)
 
            // Increase the count
            count[e % 10]++;
 
        // Mark the digit as visited
        hash[e % 10] = true;
 
        // Delete the digit
        e /= 10;
    }
}
 
// Function to find the length of subsequence which has
// atleast one digit common among all its elements
static void find_subsequence(int arr[], int n)
{
    // Count of digits
    int count[] = new int[10];
 
    // Set the initial value to zero
    //memset(count, 0, sizeof(count));
    for (int i = 0; i < n; i++) {
 
        // Extract the digits of the element
        // and increase the count
        count_(count, arr[i]);
    }
 
    // Longest subsequence
    int longest = 0;
 
    // Get the longest subsequence
    for (int i = 0; i < 10; i++)
        longest = Math.max(count[i], longest);
 
    // Print the length of longest subsequence
    System.out.print( longest);
}
 
        // Driver code
    public static void main (String[] args) {
            int arr[] = { 11, 12, 23, 74, 13 };
 
    int n =arr.length;
 
    find_subsequence(arr, n);
 
    }
}
// This code is contributed
// by shs

# Python3 program to find the length
# of subsequence which has atleast
# one digit common among all its elements
 
# If the number contains a digit increase
# the count by 1 (even if it has multiple
# same digit the count should be increased
# by only once)
def count_(count, e):
 
    # Hash to make it sure that a digit
    # is counted only once
    hash = [False] * 10
 
    # Extract the digits
    while (e > 0):
 
        # If the digit did not
        # appear before
        if (hash[e % 10] == False) :
 
            # Increase the count
            count[e % 10] += 1
 
        # Mark the digit as visited
        hash[e % 10] = True
 
        # Delete the digit
        e //= 10
 
# Function to find the length of
# subsequence which has atleast
# one digit common among all its elements
def find_subsequence(arr, n) :
 
    # Count of digits
    count = [0] * 10
 
    for i in range ( n) :
 
        # Extract the digits of the element
        # and increase the count
        count_(count, arr[i])
 
    # Longest subsequence
    longest = 0
 
    # Get the longest subsequence
    for i in range(10) :
        longest = max(count[i], longest)
 
    # Print the length of
    # longest subsequence
    print (longest)
 
# Driver code
if __name__ == "__main__":
 
    arr = [ 11, 12, 23, 74, 13 ]
 
    n = len(arr)
 
    find_subsequence(arr, n)
 
# This code is contributed
# by ChitraNayal

// C# program to find the length
// of subsequence which has atleast
// one digit common among all its elements
using System;
 
class GFG
{
 
// If the number contains a digit increase
// the count by 1 (even if it has multiple
// same digit the count should be increased
// by only once)
static void count_(int []count, int e)
{
    // Hash to make it sure that a
    // digit is counted only once
    bool []hash = new bool[10];
 
    // Set the hash to its initial value
    //memset(hash, false, sizeof(hash));
 
    // Extract the digits
    while (e > 0)
    {
 
        // If the digit did not
        // appear before
        if (hash[e % 10] == false)
 
            // Increase the count
            count[e % 10]++;
 
        // Mark the digit as visited
        hash[e % 10] = true;
 
        // Delete the digit
        e /= 10;
    }
}
 
// Function to find the length of
// subsequence which has atleast
// one digit common among all its elements
static void find_subsequence(int []arr,
                             int n)
{
    // Count of digits
    int []count = new int[10];
 
    // Set the initial value to zero
    //memset(count, 0, sizeof(count));
    for (int i = 0; i < n; i++)
    {
 
        // Extract the digits of the element
        // and increase the count
        count_(count, arr[i]);
    }
 
    // Longest subsequence
    int longest = 0;
 
    // Get the longest subsequence
    for (int i = 0; i < 10; i++)
        longest = Math.Max(count[i], longest);
 
    // Print the length of
    // longest subsequence
    Console.WriteLine(longest);
}
 
// Driver code
public static void Main ()
{
    int []arr = { 11, 12, 23, 74, 13 };
 
    int n = arr.Length;
 
    find_subsequence(arr, n);
}
}
 
// This code is contributed
// by Shashank

<script>
 
// Javascript program to find the length of subsequence which has
// atleast one digit common among all its elements
 
// If the number contains a digit increase
// the count by 1 (even if it has multiple
// same digit the count should be increased
// by only once)
function count_(count, e)
{
    // Hash to make it sure that a digit
    // is counted only once
    var hash = Array(10).fill(false);
 
    // Extract the digits
    while (e > 0) {
 
        // If the digit did not appear before
        if (hash[e % 10] == false)
 
            // Increase the count
            count[e % 10]++;
 
        // Mark the digit as visited
        hash[e % 10] = true;
 
        // Delete the digit
        e /= 10;
    }
}
 
// Function to find the length of subsequence which has
// atleast one digit common among all its elements
function find_subsequence(arr, n)
{
    // Count of digits
    var count = Array(10).fill(0);
 
    for (var i = 0; i < n; i++) {
 
        // Extract the digits of the element
        // and increase the count
        count_(count, arr[i]);
    }
 
    // Longest subsequence
    var longest = 0;
 
    // Get the longest subsequence
    for (var i = 0; i < 10; i++)
        longest = Math.max(count[i], longest);
 
    // Print the length of longest subsequence
    document.write( longest);
}
 
// Driver code
var arr = [ 11, 12, 23, 74, 13 ];
var n = arr.length;
find_subsequence(arr, n);
 
</script>   

3

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)