A pair of strings when concatenated is said to be a ‘Pandigital Concatenation’ if their concatenation consists of all digits from (0 – 9) in any order at least once.The task is, given N strings, compute the number of pairs resulting in a ‘Pandigital Concatenation’.

Examples:

Input : num[] = {"123567", "098234", "14765", "19804"} Output : 3 The pairs, 1^{st}and 2^{nd}giving (123567098234),1^{st}and 4^{rd}giving(12356719804) and 2^{nd}and 3^{rd}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.

**Method 1 (Brute Force):** A possible brute-force solution is to form all possible concatenations by forming all pairs in O(n^{2} and using a frequency array for digits (0 – 9), we check if each digit exists at least once in each concatenation formed for every pair.

// CPP 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'] = false; // 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> &arr) { // 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; }

Output:

3

**Method 2 (Efficient):**

Now we look for something better than the brute-force discussed above. Careful analysis suggests that, for every digit 0 – 9 to be present we have a mask as 1111111111 (i.e. all numbers 0-9 exist in the array of numbers

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.

So now the approach is to represent every string as a mask of 10 bits where the i^{th} bit is set if the i^{th} digit exists in the 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

The approach though may look complete is still not efficient as we still have to iterate over all pairs and check if the OR of these two strings result in the mask of a valid Pandigital Concatenation.

If we analyze the possible masks of all possible strings we can understand that every single string would be only comprised of digits 0 – 9, so every number can at max contain all digits 0 to 9 at least once thus the mask of such a number would be 1111111111 (1023 in decimal). Thus in decimal system all masks exits in (0 – 1023].

Now we just have to maintain a frequency array to store the number of times a mask exists in the array of strings.

Let two masks be i and j with frequencies freq

_{i}and freq_{j}respectively,If (i OR j) = Mask

_{pandigital concatenation}

Then,

Number of Pairs = freq_{i}* freq_{j}

// CPP 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 possiblg concatenations. return pandigitalConcatenations(freq); } // Driver code int main() { vector<string> v = {"123567", "098234", "14765", "19804"}; cout << countPandigitalPairs(v) << endl; return 0; }

Output:

3

**Complexity :** O(N * |s| + 1023 * 1023) where |s| gives length of strings in the array

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

more link ADS

Smart Retail, Smart Agriculture, Smart supply Chain, Smart Health, Smart energy, Smart City

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars

Travel Blog is a unique free online travel diary for travellers across the world.