Encuentra permutaciones binarias de tamaño dado que no están presentes en la array

Dado un entero positivo N y una array arr[] de tamaño K que consiste en una string binaria donde cada string es de tamaño N , la tarea es encontrar todas las strings binarias de tamaño N que no están presentes en la array arr[] .

Ejemplos:

Entrada: N = 3, arr[] = {“101”, “111”, “001”, “010”, “011”, “100”, “110”}
Salida: 000
Explicación: Solo 000 está ausente en el array dada.

Entrada: N = 2, arr[] = {“00”, “01”}
Salida: 10 11

Enfoque: el problema dado se puede resolver encontrando todas las strings binarias de tamaño N usando Backtracking y luego imprimiendo esas strings que no están presentes en la array arr[] . Siga los pasos a continuación para resolver el problema:

• Inicialice un conjunto_desordenado de strings S que almacene todas las strings en la array arr[] .
• Inicialice una variable, digamos total y configúrela como la potencia de 2 ^N , donde N es el tamaño de la string .
• Iterar sobre el rango [0, total) usando la variable i y realizar los siguientes pasos:
  • Inicialice una variable de string vacía num como «» .
  • Itere sobre el rango [N – 1, 0] usando la variable j y si el valor de Bitwise AND de i y 2 ^j es verdadero , entonces inserte el carácter 1 en la string num . De lo contrario, presione el carácter 0 .
  • Si num no está presente en el conjunto S , imprima la string num como la string resultante.
• Después de completar los pasos anteriores, si todas las strings binarias posibles están presentes en la array, imprima «-1» .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find a Binary String of
// same length other than the Strings
// present in the array
void findMissingBinaryString(vector<string>& nums, int N)
{
    unordered_set<string> s;
    int counter = 0;
 
    // Map all the strings present in
    // the array
    for (string str : nums) {
        s.insert(str);
    }
 
    int total = (int)pow(2, N);
    string ans = "";
 
    // Find all the substring that
    // can be made
    for (int i = 0; i < total; i++) {
        string num = "";
        for (int j = N - 1; j >= 0; j--) {
            if (i & (1 << j)) {
                num += '1';
            }
            else {
                num += '0';
            }
        }
 
        // If num already exists then
        // increase counter
        if (s.find(num) != s.end()) {
            continue;
            counter++;
        }
 
        // If not found print
        else {
            cout << num << ", ";
        }
    }
 
    // If all the substrings are present
    // then print -1
    if (counter == total) {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
    int N = 3;
    vector<string> arr
        = { "101", "111", "001", "011", "100", "110" };
 
    findMissingBinaryString(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find a Binary String of
// same length other than the Strings
// present in the array
static void findMissingBinaryString(String[] nums, int N)
{
    HashSet<String> s = new HashSet<String>();
    int counter = 0;
 
    // Map all the Strings present in
    // the array
    for (String str : nums) {
        s.add(str);
    }
 
    int total = (int)Math.pow(2, N);
    String ans = "";
 
    // Find all the subString that
    // can be made
    for (int i = 0; i < total; i++) {
        String num = "";
        for (int j = N - 1; j >= 0; j--) {
            if ((i & (1 << j))>0) {
                num += '1';
            }
            else {
                num += '0';
            }
        }
 
        // If num already exists then
        // increase counter
        if (s.contains(num)) {
             
            counter++;
            continue;
        }
 
        // If not found print
        else {
            System.out.print(num+ ", ");
        }
    }
 
    // If all the subStrings are present
    // then print -1
    if (counter == total) {
        System.out.print("-1");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
    String []arr
        = { "101", "111", "001", "011", "100", "110" };
 
    findMissingBinaryString(arr, N);
 
}
}
 
// This code is contributed by Princi Singh

# Python 3 program for the above approach
from math import pow
 
# Function to find a Binary String of
# same length other than the Strings
# present in the array
def findMissingBinaryString(nums, N):
    s = set()
    counter = 0
 
    # Map all the strings present in
    # the array
    for x in nums:
        s.add(x)
 
    total = int(pow(2, N))
    ans = ""
 
    # Find all the substring that
    # can be made
    for i in range(total):
        num = ""
        j = N - 1
        while(j >= 0):
            if (i & (1 << j)):
                num += '1'
            else:
                num += '0'
            j -= 1
 
        # If num already exists then
        # increase counter
        if (num in s):
            continue
            counter += 1
 
        # If not found print
        else:
            print(num,end = ", ")
 
    # If all the substrings are present
    # then print -1
    if (counter == total):
        print("-1")
 
# Driver Code
if __name__ == '__main__':
    N = 3
    arr = ["101", "111", "001", "011", "100", "110"]
 
    findMissingBinaryString(arr, N)
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
    // Function to find a Binary String of
    // same length other than the Strings
    // present in the array
    static void findMissingBinaryString(string[] nums,
                                        int N)
    {
        HashSet<string> s = new HashSet<string>();
        int counter = 0;
 
        // Map all the Strings present in
        // the array
        foreach(string str in nums) { s.Add(str); }
 
        int total = (int)Math.Pow(2, N);
        // string ans = "";
 
        // Find all the subString that
        // can be made
        for (int i = 0; i < total; i++) {
            string num = "";
            for (int j = N - 1; j >= 0; j--) {
                if ((i & (1 << j)) > 0) {
                    num += '1';
                }
                else {
                    num += '0';
                }
            }
 
            // If num already exists then
            // increase counter
            if (s.Contains(num)) {
 
                counter++;
                continue;
            }
 
            // If not found print
            else {
                Console.Write(num + ", ");
            }
        }
 
        // If all the subStrings are present
        // then print -1
        if (counter == total) {
            Console.Write("-1");
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 3;
        string[] arr
            = { "101", "111", "001", "011", "100", "110" };
 
        findMissingBinaryString(arr, N);
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for the above approach
 
// Function to find a Binary String of
// same length other than the Strings
// present in the array
function findMissingBinaryString(nums, N) {
  let s = new Set();
  let counter = 0;
 
  // Map all the strings present in
  // the array
  for (let str of nums) {
    s.add(str);
  }
 
  let total = Math.pow(2, N);
  let ans = "";
 
  // Find all the substring that
  // can be made
  for (let i = 0; i < total; i++) {
    let num = "";
    for (let j = N - 1; j >= 0; j--) {
      if (i & (1 << j)) {
        num += "1";
      } else {
        num += "0";
      }
    }
 
    // If num already exists then
    // increase counter
    if (s.has(num)) {
      continue;
      counter++;
    }
 
    // If not found print
    else {
      document.write(num + ", ");
    }
  }
 
  // If all the substrings are present
  // then print -1
  if (counter == total) {
    document.write("-1");
  }
}
 
// Driver Code
let N = 3;
let arr = ["101", "111", "001", "011", "100", "110"];
 
findMissingBinaryString(arr, N);
 
// This code is contributed by _saurabh_jaiswal.
</script>

000, 010,

Complejidad de tiempo: O(N*2 ^N )
Espacio auxiliar: O(K), donde K es el tamaño de la array