Find any permutation that does not exist in a binary string array of given size

In this problem, we need to find all missing binary strings of length N from an array. We can solve this problem by finding all permutations of a binary string of length N and checking which permutations do not exist in the array. Here we will see iterative and recursive methods to solve this problem.

Problem Statement - We have been given an array arr[] of length N containing binary strings of different lengths. We need to find all missing binary strings of length N from the array.

Example Example

Input – arr = {"111", "001", "100", "110"}, N = 3

Output – [000, 010, 011, 101]

Explanation – There are 8 binary strings of length 3, because 2 raised to the third power is equal to 8. So, it prints out the missing 4 binary strings of length 3.

Input – str = {‘00’, ‘10’, ‘11’}, N = 2

Output –[‘01’]

Explanation – ‘01’ is missing in the array, so it will be printed in the output.

method one

Here, we will use the iterative method to find all possible binary strings of length N. After that we will check if the string exists in the array. If it doesn't exist, we print the string.

algorithm

• Define a collection and use the insert() method to add all the strings in the array to the collection.

• Initialize the total variable with 2N, where 2N is the total number of strings of length N

• Define variable 'cnt' and initialize it to zero to store the total number of missing combinations.

• Use a loop to make 'total' number of iterations to find all binary strings of length N.

• In the loop, initialize the "num" string variable with an empty string.

• Use nested loops for a total of N iterations, and starting from the last iteration, create a string of length N.

• Use the find() method to check whether the collection contains the current string. If so, increase the value of 'cnt' by 1.

• If the string is not in the map, print it to appear in the output

• If the value of "cnt" is equal to the total number, it means that all strings of length N exist in the array, and "-1" is printed.

Example

#include <bits/stdc++.h>
using namespace std;
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {
   unordered_set<string> set;
   // insert all the strings in the set
   for (string temp : arr) {
      set.insert(temp);
   }
   // get total combinations for the string of length N
   int total = (int)pow(2, N);
   // To store combinations that are present in an array
   int cnt = 0;
   // find all the combinations
   for (int p = 0; p < total; p++) {
      // Initialize empty binary string
      string bin = "";
      for (int q = N - 1; q >= 0; q--) {
          // If the qth bit is set, append '1'; append '0'.
          if (p & (1 << q)) {
              bin += '1';
          } else {
              bin += '0';
          }
      }
      // If the combination is present in an array, increment cnt
      if (set.find(bin) != set.end()) {
          cnt++;
          continue;
      } else {
          cout << bin << ", ";
      }
   }
   // If all combinations are present in an array, print -1
   if (cnt == total) {
      cout << "-1";
   }
}
int main() {
   int N = 3;
   vector<string> arr = {"111", "001", "100", "110"};
   printMissingCombinations(arr, N);
   return 0;
}

Output

000, 010, 011, 101, 

Time complexity - O(N*2N), where O(N) is used to check whether the string exists in the array and O(2N) is used to find all possible permutations.

Space complexity - O(N), because we use set to store strings.

Method Two

In this approach, we show the use of a recursive approach to find all possible binary strings of length N.

algorithm

• Define a collection and insert all array values ​​into the collection.

• Call the generateCombinations() function to generate all combinations of binary strings

• Define the base case in the generateCombinations() function. If the index is equal to N, then currentCombination is added to the list.

• After adding '0' or '1' to the current combination, call the generateCombinations() function recursively.

• After getting all combinations, check which combinations exist in the array and which do not. Also, print out the missing combinations to show in the output.

Example

#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible combinations of binary strings
void generateCombinations(int index, int N, string currentCombination, vector<string> &combinations) {
   // Base case: if we have reached the desired length N, add the combination to the vector
   if (index == N) {
      combinations.push_back(currentCombination);
      return;
   }
   // Recursively generate combinations by trying both 0 and 1 at the current index
   generateCombinations(index + 1, N, currentCombination + "0", combinations);
   generateCombinations(index + 1, N, currentCombination + "1", combinations);
}
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {    
   unordered_set<string> set;
   // insert all the strings in the set
   for (string str : arr) {
      set.insert(str);
   }
   // generating all combinations of binary strings of length N
   vector<string> combinations;
   generateCombinations(0, N, "", combinations);
   // Traverse all the combinations and check if it is present in the set or not
   for (string str : combinations) {
      // If the combination is not present in the set, print it
      if (set.find(str) == set.end()) {
          cout << str << endl;
      }
   }

   return;
}
int main(){
   int N = 3;
   vector<string> arr = {"111", "001", "100", "110"};
   printMissingCombinations(arr, N);
   return 0;
}

Output

000
010
011
101

Time complexity - O(N*2N)

Space complexity - O(2N) since we store all combinations in arrays.

Both methods use the same logic to solve the problem. The first method uses an iterative technique to find all combinations of a binary string of length N, which is faster than the recursive technique used in the second method. Also, the second method consumes more space than the first method.

The above is the detailed content of Find any permutation that does not exist in a binary string array of given size. For more information, please follow other related articles on the PHP Chinese website!