Encuentre cualquier permutación de Binary String de tamaño dado que no esté presente en Array

Dada una array arr[] de N strings binarias distintas, cada una con N caracteres, la tarea es encontrar cualquier string binaria que tenga N caracteres de modo que no aparezca en la array dada arr[] .

Ejemplo:

Entrada: arr[] = {“10”, “01”}
Salida: 00
Explicación: la string “00” no aparece en la array arr[]. Otra string válida puede ser «11», que tampoco aparece en la array arr[].

Entrada: arr[] {“111”, “011”, “001”}
Salida: 101
Explicación: la string “101” no aparece en la array arr[]. Otras strings válidas son «000», «010», «100» y «110».

Enfoque ingenuo: el problema dado se puede resolver generando todas las strings binarias que tienen N bits y devolviendo la ^primera string de manera que no ocurra en la array dada arr[] .

Complejidad de Tiempo: O(2 ^N * N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el problema dado se puede optimizar mediante el uso de un método similar al argumento diagonal de Cantor. Se puede observar que la string resultante debe tener al menos un bit diferente de todas las strings en arr[] . Por lo tanto, la string binaria resultante se puede construir tomando el complemento del ^1er elemento de la ^1ra string como el ^1er elemento, el complemento del ^2do elemento de la ^2da string como el ^2do elemento, y así sucesivamente. . A continuación se detallan los pasos a seguir:

• Cree una string ans , que almacena la string resultante. Inicialmente, está vacío.
• Iterar a través de las strings dadas en orden diagonal, es decir, ^1er elemento de la ^1ra string, ^2do elemento de la ^2da string, y así sucesivamente, y agregar el complemento del valor en el índice actual en la string ans .
• La string almacenada en ans después de iterar a través de la array completa arr[] es una de las strings válidas requeridas.

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
// N bits that does not occur in the
// given array arr[]
string findString(vector<string>& arr, int N)
{
    // Stores the resultant string
    string ans = "";
 
    // Loop to iterate over all the given
    // strings in a diagonal order
    for (int i = 0; i < N; i++) {
 
        // Append the complement of element
        // at current index into ans
        ans += arr[i][i] == '0' ? '1' : '0';
    }
 
    // Return Answer
    return ans;
}
 
// Driver code
int main()
{
    vector<string> arr{ "111", "011", "001" };
    int N = arr.size();
 
    cout << findString(arr, N);
 
    return 0;
}

// Java Program for the above approach
 
import java.io.*;
 
class GFG {
   
      // Function to find a binary string of
    // N bits that does not occur in the
    // given array arr[]
    static String findString(String arr[], int N)
    {
        // Stores the resultant string
        String ans = "";
 
        // Loop to iterate over all the given
        // strings in a diagonal order
        for (int i = 0; i < N; i++) {
 
            // Append the complement of element
            // at current index into ans
            ans += arr[i].charAt(i) == '0' ? '1' : '0';
        }
 
        // Return Answer
        return ans;
    }
 
    // Driver code
    public static void main (String[] args) {
           String arr[] = { "111", "011", "001" };
        int N = arr.length;
 
        System.out.println(findString(arr, N));
    }
}
 
// This code is contributed by Dharanendra L V.

# Python 3 Program for the above approach
 
# Function to find a binary string of
# N bits that does not occur in the
# given array arr[]
def findString(arr, N):
   
    # Stores the resultant string
    ans = ""
 
    # Loop to iterate over all the given
    # strings in a diagonal order
    for i in range(N):
       
        # Append the complement of element
        # at current index into ans
        ans += '1' if arr[i][i] == '0' else '0'
 
    # Return Answer
    return ans
 
# Driver code
if __name__ == '__main__':
    arr = ["111", "011", "001"]
    N = len(arr)
 
    print(findString(arr, N))
 
    # This code is contributed by bgangwar59.

// C# Program for the above approach
using System;
 
class GFG {
 
    // Function to find a binary string of
    // N bits that does not occur in the
    // given array arr[]
    static string findString(string[] arr, int N)
    {
       
        // Stores the resultant string
        string ans = "";
 
        // Loop to iterate over all the given
        // strings in a diagonal order
        for (int i = 0; i < N; i++) {
 
            // Append the complement of element
            // at current index into ans
            ans += arr[i][i] == '0' ? '1' : '0';
        }
 
        // Return Answer
        return ans;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        string[] arr = { "111", "011", "001" };
        int N = arr.Length;
 
        Console.WriteLine(findString(arr, N));
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find a binary string of
        // N bits that does not occur in the
        // given array arr[]
        function findString(arr, N)
        {
         
            // Stores the resultant string
            let ans = "";
 
            // Loop to iterate over all the given
            // strings in a diagonal order
            for (let i = 0; i < N; i++) {
 
                // Append the complement of element
                // at current index into ans
                ans += arr[i][i] == '0' ? '1' : '0';
            }
 
            // Return Answer
            return ans;
        }
 
        // Driver code
        let arr = ["111", "011", "001"];
        let N = arr.length;
 
        document.write(findString(arr, N));
 
     // This code is contributed by Potta Lokesh
 
    </script>

000

Complejidad temporal: O(N)
Espacio auxiliar: O(1)