Se dice que un par de strings cuando se concatenan es una ‘Concatenación pandigital’ si su concatenación consta de todos los dígitos de (0 a 9) en cualquier orden al menos una vez. La tarea es, dadas N strings, calcular el número de pares que dan como resultado una ‘Concatenación pandigital’.
Ejemplos:
Input : num[] = {"123567", "098234", "14765", "19804"}
Output : 3
The pairs, 1st and 2nd giving
(123567098234),1st and 4rd giving(12356719804) and
2nd and 3rd giving (09823414765),
on concatenation result in Pandigital Concatenations.
Input : num[] = {"56789", "098345", "1234"}
Output : 0
None of the pairs on concatenation result in Pandigital
Concatenations.
Método 1 (Fuerza bruta): una posible solución de fuerza bruta es formar todas las concatenaciones posibles formando todos los pares en O(n 2 y usando una array de frecuencia para los dígitos (0 – 9), verificamos si cada dígito existe al menos una vez en cada concatenación formada para cada par.
C++
// C++ program to find all
// Pandigital concatenations
// of two strings.
#include <bits/stdc++.h>
using namespace std;
// Checks if a given
// string is Pandigital
bool isPanDigital(string s)
{
bool digits[10] = {false};
for (int i = 0; i < s.length(); i++)
digits[s[i] - '0'] = true;
// digit i is not present
// thus not pandigital
for (int i = 0; i <= 9; i++)
if (digits[i] == false)
return false;
return true;
}
// Returns number of pairs
// of strings resulting in
// Pandigital Concatenations
int countPandigitalPairs(vector<string> &v)
{
// iterate over all
// pair of strings
int pairs = 0;
for (int i = 0; i < v.size(); i++)
for (int j = i + 1; j < v.size(); j++)
if (isPanDigital(v[i] + v[j]))
pairs++;
return pairs;
}
// Driver code
int main()
{
vector<string> v = {"123567", "098234",
"14765", "19804"};
cout << countPandigitalPairs(v) << endl;
return 0;
}
Java
// Java program to find all
// Pandigital concatenations
// of two strings.
import java.io.*;
import java.util.*;
class GFG
{
static ArrayList<String> v =
new ArrayList<String>();
// Checks if a given
// string is Pandigital
static int isPanDigital(String s)
{
int digits[] = new int[10];
for (int i = 0; i < s.length(); i++)
digits[s.charAt(i) -
(int)'0'] = 1;
// digit i is not present
// thus not pandigital
for (int i = 0; i <= 9; i++)
if (digits[i] == 0)
return 0;
return 1;
}
// Returns number of pairs
// of strings resulting in
// Pandigital Concatenations
static int countPandigitalPairs()
{
// iterate over all
// pair of strings
int pairs = 0;
for (int i = 0; i < v.size(); i++)
for (int j = i + 1;
j < v.size(); j++)
if (isPanDigital(v.get(i) +
v.get(j)) == 1)
pairs++;
return pairs;
}
// Driver code
public static void main(String args[])
{
v.add("123567");
v.add("098234");
v.add("14765");
v.add("19804");
System.out.print(countPandigitalPairs());
}
}
// This code is contributed
// by Manish Shaw(manishshaw1)
Python3
# Python3 program to find all
# Pandigital concatenations
# of two strings.
# Checks if a given
# is Pandigital
def isPanDigital(s) :
digits = [False] * 10;
for i in range(0, len(s)) :
digits[int(s[i]) -
int('0')] = True
# digit i is not present
# thus not pandigital
for i in range(0, 10) :
if (digits[i] == False) :
return False
return True
# Returns number of pairs
# of strings resulting in
# Pandigital Concatenations
def countPandigitalPairs(v) :
# iterate over all
# pair of strings
pairs = 0
for i in range(0, len(v)) :
for j in range (i + 1,
len(v)) :
if (isPanDigital(v[i] +
v[j])) :
pairs = pairs + 1
return pairs
# Driver code
v = ["123567", "098234",
"14765", "19804"]
print (countPandigitalPairs(v))
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# program to find all Pandigital
// concatenations of two strings.
using System;
using System.Collections.Generic;
class GFG
{
// Checks if a given
// string is Pandigital
static int isPanDigital(string s)
{
int []digits = new int[10];
Array.Clear(digits, 0, 10);
for (int i = 0; i < s.Length; i++)
digits[s[i] - (int)'0'] = 1;
// digit i is not present
// thus not pandigital
for (int i = 0; i <= 9; i++)
if (digits[i] == 0)
return 0;
return 1;
}
// Returns number of pairs
// of strings resulting in
// Pandigital Concatenations
static int countPandigitalPairs(ref List<string> v)
{
// iterate over all
// pair of strings
int pairs = 0;
for (int i = 0; i < v.Count; i++)
for (int j = i + 1; j < v.Count; j++)
if (isPanDigital(v[i] + v[j]) == 1)
pairs++;
return pairs;
}
// Driver code
static void Main()
{
List<string> v = new List<string>{"123567", "098234",
"14765", "19804"};
Console.WriteLine(countPandigitalPairs(ref v));
}
}
// This code is contributed
// by Manish Shaw(manishshaw1)
PHP
<?php
// PHP program to find all
// Pandigital concatenations
// of two strings.
// Checks if a given
// $is Pandigital
function isPanDigital($s)
{
$digits = array();
$digits = array_fill(0, 10, false);
for ($i = 0; $i < strlen($s); $i++)
$digits[ord($s[$i]) -
ord('0')] = true;
// digit i is not present
// thus not pandigital
for ($i = 0; $i <= 9; $i++)
if ($digits[$i] == false)
return false;
return true;
}
// Returns number of pairs
// of strings resulting in
// Pandigital Concatenations
function countPandigitalPairs(&$v)
{
// iterate over all
// pair of strings
$pairs = 0;
for ($i = 0;
$i < count($v); $i++)
{
for ($j = $i + 1;
$j < count($v); $j++)
{
if (isPanDigital($v[$i].$v[$j]))
{
$pairs++;
}
}
}
return $pairs;
}
// Driver code
$v = array("123567", "098234",
"14765", "19804");
echo (countPandigitalPairs($v));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to find all
// Pandigital concatenations
// of two strings.
// Checks if a given
// is Pandigital
function isPanDigital(s)
{
let digits = new Array(10).fill(false);
for(let i = 0; i < s.length; i++)
digits[s[i].charCodeAt(0) -
'0'.charCodeAt(0)] = true;
// digit i is not present
// thus not pandigital
for(let i = 0; i <= 9; i++)
if (digits[i] == false)
return false;
return true;
}
// Returns number of pairs
// of strings resulting in
// Pandigital Concatenations
function countPandigitalPairs(v)
{
// Iterate over all
// pair of strings
let pairs = 0;
for(let i = 0; i < v.length; i++)
{
for(let j = i + 1;
j < v.length; j++)
{
if (isPanDigital(v[i] + v[j]))
{
pairs++;
}
}
}
return pairs;
}
// Driver code
let v = [ "123567", "098234",
"14765", "19804" ];
document.write(countPandigitalPairs(v));
// This code is contributed by gfgking
</script>
Producción:
3
Método 2 (Eficiente):
Ahora buscamos algo mejor que la fuerza bruta discutida anteriormente. Un análisis cuidadoso sugiere que, para que esté presente cada dígito del 0 al 9, tenemos una máscara como 1111111111 (es decir, todos los números del 0 al 9 existen en la array de números).
Digits - 0 1 2 3 4 5 6 7 8 9
| | | | | | | | | |
Mask - 1 1 1 1 1 1 1 1 1 1
Here 1 denotes that the corresponding digits
exists at-least once thus for all such Pandigital
Concatenations, this relationship should hold.
So we can represent 11...11 as a valid mask for
pandigital concatenations.
Así que ahora el enfoque es representar cada string como una máscara de 10 bits donde el i -ésimo bit se establece si el i -ésimo dígito existe en la string.
E.g., "11405" can be represented as
Digits - 0 1 2 3 4 5 6 7 8 9
| | | | | | | | | |
Mask for 11405 - 1 1 0 0 1 1 0 0 0 0
Aunque el enfoque puede parecer completo, todavía no es eficiente, ya que todavía tenemos que iterar sobre todos los pares y verificar si el OR de estas dos strings da como resultado la máscara de una concatenación pandigital válida.
Si analizamos las posibles máscaras de todas las strings posibles, podemos entender que cada string individual estaría compuesta solo por dígitos 0 a 9, por lo que cada número puede contener como máximo todos los dígitos 0 a 9 al menos una vez, por lo que la máscara de tal número sería sea 1111111111 (1023 en decimal). Así, en el sistema decimal todas las máscaras salen en (0 – 1023).
Ahora solo tenemos que mantener una array de frecuencias para almacenar la cantidad de veces que existe una máscara en la array de strings.
Sean dos máscaras i y j con frecuencias freq i y freq j respectivamente,
Si (i O j) = Concatenación pandigital
de máscara Entonces,
Número de pares = freq i * freq j
C++
// C++ program to count PanDigital pairs
#include <bits/stdc++.h>
using namespace std;
const int pandigitalMask = ((1 << 10) - 1);
void computeMaskFrequencies(vector<string> v, map<int,
int>& freq)
{
for (int i = 0; i < v.size(); i++) {
int mask = 0;
// Stores digits present in string v[i]
// atleast once. We use a set as we only
// need digits which exist only once
// (irrespective of reputation)
unordered_set<int> digits;
for (int j = 0; j < v[i].size(); j++)
digits.insert(v[i][j] - '0');
// Calculate the mask by considering all digits
// existing atleast once
for (auto it = digits.begin(); it != digits.end(); it++) {
int digit = (*it);
mask += (1 << digit);
}
// Increment the frequency of this mask
freq[mask]++;
}
}
// Returns number of pairs of strings resulting
// in Pandigital Concatenations
int pandigitalConcatenations(map<int, int> freq)
{
int ans = 0;
// All possible strings lie between 1 and 1023
// so we iterate over every possible mask
for (int i = 1; i <= 1023; i++) {
for (int j = 1; j <= 1023; j++) {
// if the concatenation results in mask of
// Pandigital Concatenation, calculate all
// pairs formed with Masks i and j
if ((i | j) == pandigitalMask) {
if (i == j)
ans += (freq[i] * (freq[i] - 1));
else
ans += (freq[i] * freq[j]);
}
}
}
// since every pair is considers twice,
// we get rid of half of these
return ans/2;
}
int countPandigitalPairs(vector<string> v)
{
// Find frequencies of all masks in
// given vector of strings
map<int, int> freq;
computeMaskFrequencies(v, freq);
// Return all possible concatenations.
return pandigitalConcatenations(freq);
}
// Driver code
int main()
{
vector<string> v = {"123567", "098234", "14765", "19804"};
cout << countPandigitalPairs(v) << endl;
return 0;
}
Java
// Java program to count PanDigital pairs
import java.util.*;
class GFG{
static int pandigitalMask = ((1 << 10) - 1);
static void computeMaskFrequencies(Vector<String> v,
HashMap<Integer, Integer> freq)
{
for(int i = 0; i < v.size(); i++)
{
int mask = 0;
// Stores digits present in String v[i]
// atleast once. We use a set as we only
// need digits which exist only once
// (irrespective of reputation)
HashSet<Integer> digits = new HashSet<>();
for(int j = 0; j < v.get(i).length(); j++)
digits.add(v.get(i).charAt(j) - '0');
// Calculate the mask by considering
// all digits existing atleast once
for(int it :digits)
{
int digit = (it);
mask += (1 << digit);
}
// Increment the frequency of
// this mask
if (freq.containsKey(mask))
{
freq.put(mask, freq.get(mask) + 1);
}
else
{
freq.put(mask, 1);
}
}
}
// Returns number of pairs of Strings
// resulting in Pandigital Concatenations
static int pandigitalConcatenations(
HashMap<Integer, Integer> freq)
{
int ans = 0;
// All possible Strings lie between
// 1 and 1023 so we iterate over every
// possible mask
for(int i = 1; i <= 1023; i++)
{
for(int j = 1; j <= 1023; j++)
{
// If the concatenation results in mask of
// Pandigital Concatenation, calculate all
// pairs formed with Masks i and j
if ((i | j) == pandigitalMask &&
freq.containsKey(j) &&
freq.containsKey(i))
{
if (i == j)
ans += (freq.get(i) *
(freq.get(i) - 1));
else
ans += (freq.get(i) *
freq.get(j));
}
}
}
// Since every pair is considers twice,
// we get rid of half of these
return ans / 2;
}
static int countPandigitalPairs(Vector<String> v)
{
// Find frequencies of all masks in
// given vector of Strings
HashMap<Integer,Integer> freq = new HashMap<>();
computeMaskFrequencies(v, freq);
// Return all possible concatenations.
return pandigitalConcatenations(freq);
}
// Driver code
public static void main(String[] args)
{
Vector<String> v = new Vector<>();
v.add("123567");
v.add("098234");
v.add("14765");
v.add("19804");
System.out.print(countPandigitalPairs(v) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python program to count PanDigital pairs pandigitalMask = ((1 << 10) - 1) freq = dict() def computeMaskFrequencies(v): global freq for i in range(len(v)): mask = 0 # Stores digits present in string v[i] # atleast once. We use a set as we only # need digits which exist only once # (irrespective of reputation) digits = set() for j in range(len(v[i])): digits.add(int(v[i][j])) # Calculate the mask by considering # all digits existing atleast once for it in digits: digit = it mask += (1 << digit) # Increment the frequency of this mask if mask in freq: freq[mask] += 1 else: freq[mask] = 1 # Returns number of pairs of strings resulting # in Pandigital Concatenations def pandigitalConcatenations(): global freq ans = 0 # All possible strings lie between 1 and 1023 # so we iterate over every possible mask for i in range(1, 1024): for j in range(1, 1024): # if the concatenation results in mask of # Pandigital Concatenation, calculate all # pairs formed with Masks i and j if ((i | j) == pandigitalMask and i in freq and j in freq): if (i == j): ans += (freq[i] * (freq[i] - 1)) else: ans += (freq[i] * freq[j]) # Since every pair is considers twice, # we get rid of half of these return ans // 2 def countPandigitalPairs(v): # Find frequencies of all masks in # given vector of strings computeMaskFrequencies(v) # Return all possible concatenations. return pandigitalConcatenations() # Driver code v = ["123567", "098234", "14765", "19804"] print(countPandigitalPairs(v)) # This code is contributed by phasing17
C#
// C# program to count
// PanDigital pairs
using System;
using System.Collections.Generic;
class GFG{
static int pandigitalMask =
((1 << 10) - 1);
static void computeMaskFrequencies(List<String> v,
Dictionary<int,
int> freq)
{
for(int i = 0; i < v.Count; i++)
{
int mask = 0;
// Stores digits present in String v[i]
// atleast once. We use a set as we only
// need digits which exist only once
// (irrespective of reputation)
HashSet<int> digits = new HashSet<int>();
for(int j = 0; j < v[i].Length; j++)
digits.Add(v[i][j] - '0');
// Calculate the mask by considering
// all digits existing atleast once
foreach(int it in digits)
{
int digit = (it);
mask += (1 << digit);
}
// Increment the frequency of
// this mask
if (freq.ContainsKey(mask))
{
freq[mask]++;
}
else
{
freq.Add(mask, 1);
}
}
}
// Returns number of pairs of
// Strings resulting in Pandigital
// Concatenations
static int pandigitalConcatenations(Dictionary<int,
int> freq)
{
int ans = 0;
// All possible Strings lie between
// 1 and 1023 so we iterate over every
// possible mask
for(int i = 1; i <= 1023; i++)
{
for(int j = 1; j <= 1023; j++)
{
// If the concatenation results in
// mask of Pandigital Concatenation,
// calculate all pairs formed with
// Masks i and j
if ((i | j) == pandigitalMask &&
freq.ContainsKey(j) &&
freq.ContainsKey(i))
{
if (i == j)
ans += (freq[i] *
(freq[i] - 1));
else
ans += (freq[i] *
freq[j]);
}
}
}
// Since every pair is considers
// twice, we get rid of half of
// these
return ans / 2;
}
static int countPandigitalPairs(List<String> v)
{
// Find frequencies of all masks in
// given vector of Strings
Dictionary<int,
int> freq = new Dictionary<int,
int>();
computeMaskFrequencies(v, freq);
// Return all possible concatenations.
return pandigitalConcatenations(freq);
}
// Driver code
public static void Main(String[] args)
{
List<String> v = new List<String>();
v.Add("123567");
v.Add("098234");
v.Add("14765");
v.Add("19804");
Console.Write(countPandigitalPairs(v) + "\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to count PanDigital pairs
const pandigitalMask = ((1 << 10) - 1);
function computeMaskFrequencies(v, freq)
{
for(let i = 0; i < v.length; i++)
{
let mask = 0;
// Stores digits present in string v[i]
// atleast once. We use a set as we only
// need digits which exist only once
// (irrespective of reputation)
let digits = new Set();
for(let j = 0; j < v[i].length; j++)
digits.add((v[i][j]).charCodeAt(0) -
'0'.charCodeAt(0));
// Calculate the mask by considering
// all digits existing atleast once
for(let it of digits)
{
let digit = it;
mask += (1 << digit);
}
// Increment the frequency of this mask
if (freq.has(mask))
{
freq.set(mask, freq.get(mask) + 1)
}
else
{
freq.set(mask, 1)
}
}
}
// Returns number of pairs of strings resulting
// in Pandigital Concatenations
function pandigitalConcatenations(freq)
{
let ans = 0;
// All possible strings lie between 1 and 1023
// so we iterate over every possible mask
for(let i = 1; i <= 1023; i++)
{
for(let j = 1; j <= 1023; j++)
{
// if the concatenation results in mask of
// Pandigital Concatenation, calculate all
// pairs formed with Masks i and j
if ((i | j) == pandigitalMask &&
freq.has(i) && freq.has(j))
{
if (i == j)
ans += (freq.get(i) *
(freq.get(i) - 1));
else
ans += (freq.get(i) *
freq.get(j));
}
}
}
// Since every pair is considers twice,
// we get rid of half of these
return Math.floor(ans / 2);
}
function countPandigitalPairs(v)
{
// Find frequencies of all masks in
// given vector of strings
let freq = new Map();
computeMaskFrequencies(v, freq);
// Return all possible concatenations.
return pandigitalConcatenations(freq);
}
// Driver code
let v = [ "123567", "098234", "14765", "19804" ];
document.write(countPandigitalPairs(v) + "<br>");
// This code is contributed by gfgking
</script>
Producción:
3
Complejidad : O(N * |s| + 1023 * 1023) donde |s| da la longitud de las strings en la array