Dada una array de n números. La tarea es encontrar el número de pares que se pueden tomar de lo dado que, al concatenar, contendrá todos los dígitos del 0 al 9.
Ejemplos:
Entrada: num[][] = { “129300455”, “5559948277”, “012334556”, “56789”, “123456879” }
Salida: 5
{“129300455”, “56789”}, { “129300455”, “123456879” }, {“5559948277”, “012334556”},
{“012334556”, “56789”}, {“012334556”, “123456879”} son el par que contiene todos los dígitos del 0 al 9 en la concatenación.
Nota: El número del dígito en cada uno de los números puede ser 10^6.
La idea es representar cada número como la máscara de 10 bits, de modo que si contiene el dígito i al menos una vez, el i -ésimo bit se establecerá en la máscara.
Por ejemplo, sea n
= 4556120 y luego se configurarán en la máscara los bits 0 , 1 , 2 , 4 , 5 y 6 . Por lo tanto, máscara = (0001110111) 2 = (119) 10 Ahora, para cada máscara m de 0 a 2^10 – 1, almacenaremos la cuenta del número de números que tienen la máscara de su número igual a m .
Entonces, haremos una array, digamos cnt[], donde cnt[i] almacena el conteo del número de números cuya máscara es igual a i. Pseudocódigo para esto:
for (i = 0; i < (1 << 10); i++)
cnt[i] = 0;
for (i = 1; i <= n; i++)
{
string x = p[i];
int mask = 0;
for (j = 0; j < x.size(); j++)
mask |= (1 << (x[j] - '0';);
cnt[mask]++;
}
Un par de números tendrá todos los dígitos del 0 al 9 si cada bit del 0 al 9 se establece en el OR bit a bit de la máscara de ambos números, es decir, si es igual a (1111111111) 2</sub) = (1023)10
Ahora, iteraremos sobre todos los pares de máscaras cuyo OR bit a bit sea igual a 1023 y agregaremos varias formas.
A continuación se muestra la implementación de este enfoque:
C++
// C++ Program to find number of pairs whose
// concatenation contains all digits from 0 to 9.
#include <bits/stdc++.h>
using namespace std;
#define N 20
// Function to return number of pairs whose
// concatenation contain all digits from 0 to 9
int countPair(char str[N][N], int n)
{
int cnt[1 << 10] = { 0 };
// making the mask for each of the number.
for (int i = 0; i < n; i++) {
int mask = 0;
for (int j = 0; str[i][j] != '\0'; ++j)
mask |= (1 << (str[i][j] - '0'));
cnt[mask]++;
}
// for each of the possible pair which can
// make OR value equal to 1023
int ans = 0;
for (int m1 = 0; m1 <= 1023; m1++)
for (int m2 = 0; m2 <= 1023; m2++)
if ((m1 | m2) == 1023) {
// finding the count of pair
// from the given numbers.
ans += ((m1 == m2) ?
(cnt[m1] * (cnt[m1] - 1)) :
(cnt[m1] * cnt[m2]));
}
return ans / 2;
}
// Driven Program
int main()
{
int n = 5;
char str[][N] = { "129300455", "5559948277",
"012334556", "56789", "123456879" };
cout << countPair(str, n) << endl;
return 0;
}
Java
// Java Program to find number of pairs whose
// concatenation contains all digits from 0 to 9.
class GFG
{
static final int N = 20;
// Function to return number of pairs whose
// concatenation contain all digits from 0 to 9
static int countPair(char str[][], int n)
{
int[] cnt = new int[1 << 10];
// making the mask for each of the number.
for (int i = 0; i < n; i++)
{
int mask = 0;
for (int j = 0; j < str[i].length; ++j)
mask |= (1 << (str[i][j] - '0'));
cnt[mask]++;
}
// for each of the possible pair which can
// make OR value equal to 1023
int ans = 0;
for (int m1 = 0; m1 <= 1023; m1++)
for (int m2 = 0; m2 <= 1023; m2++)
if ((m1 | m2) == 1023)
{
// finding the count of pair
// from the given numbers.
ans += ((m1 == m2) ? (cnt[m1] * (cnt[m1] - 1)) :
(cnt[m1] * cnt[m2]));
}
return ans / 2;
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
char str[][] = { "129300455".toCharArray(),
"5559948277".toCharArray(),
"012334556".toCharArray(),
"56789".toCharArray(),
"123456879".toCharArray() };
System.out.print(countPair(str, n) + "\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 Program to find
# number of pairs whose
# concatenation contains
# all digits from 0 to 9.
N = 20
# Function to return number
# of pairs whose concatenation
# contain all digits from 0 to 9
def countPair(st, n):
cnt = [0] * (1 << 10)
# Making the mask for
# each of the number.
for i in range (n):
mask = 0
for j in range (len(st[i])):
mask |= (1 << (ord(st[i][j]) - ord('0')))
cnt[mask] += 1
# for each of the possible
# pair which can make OR
# value equal to 1023
ans = 0
for m1 in range(1024):
for m2 in range (1024):
if ((m1 | m2) == 1023):
# Finding the count of pair
# from the given numbers.
if (m1 == m2):
ans += (cnt[m1] * (cnt[m1] - 1))
else:
ans += (cnt[m1] * cnt[m2])
return ans // 2
# Driven Program
if __name__ == "__main__":
n = 5
st = ["129300455", "5559948277",
"012334556", "56789", "123456879"]
print(countPair(st, n))
# This code is contributed by Chitranayal
C#
// C# Program to find number of pairs whose
// concatenation contains all digits from 0 to 9.
using System;
class GFG
{
static readonly int N = 20;
// Function to return number of pairs whose
// concatenation contain all digits from 0 to 9
static int countPair(String []str, int n)
{
int[] cnt = new int[1 << 10];
// making the mask for each of the number.
for (int i = 0; i < n; i++)
{
int mask = 0;
for (int j = 0; j < str[i].Length; ++j)
mask |= (1 << (str[i][j] - '0'));
cnt[mask]++;
}
// for each of the possible pair which can
// make OR value equal to 1023
int ans = 0;
for (int m1 = 0; m1 <= 1023; m1++)
for (int m2 = 0; m2 <= 1023; m2++)
if ((m1 | m2) == 1023)
{
// finding the count of pair
// from the given numbers.
ans += ((m1 == m2) ? (cnt[m1] * (cnt[m1] - 1)) :
(cnt[m1] * cnt[m2]));
}
return ans / 2;
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
String []str = {"129300455",
"5559948277",
"012334556",
"56789",
"123456879" };
Console.Write(countPair(str, n) + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript Program to find number of pairs whose
// concatenation contains all digits from 0 to 9.
let N = 20;
// Function to return number of pairs whose
// concatenation contain all digits from 0 to 9
function countPair(str,n)
{
let cnt = new Array(1 << 10);
for(let i=0;i<cnt.length;i++)
{
cnt[i]=0;
}
// making the mask for each of the number.
for (let i = 0; i < n; i++)
{
let mask = 0;
for (let j = 0; j < str[i].length; ++j)
mask |= (1 << (str[i][j] - '0'));
cnt[mask]++;
}
// for each of the possible pair which can
// make OR value equal to 1023
let ans = 0;
for (let m1 = 0; m1 <= 1023; m1++)
for (let m2 = 0; m2 <= 1023; m2++)
if ((m1 | m2) == 1023)
{
// finding the count of pair
// from the given numbers.
ans += ((m1 == m2) ? (cnt[m1] * (cnt[m1] - 1)) :
(cnt[m1] * cnt[m2]));
}
return Math.floor(ans / 2);
}
// Driver Code
let n = 5;
let st = ["129300455", "5559948277",
"012334556", "56789", "123456879"];
document.write(countPair(st, n))
// This code is contributed by avanitrachhadiya2155
</script>
5
Complejidad : O(n + 2^10 * 2^10)