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++
// 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
// 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
Python3
# 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#
// 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.
Javascript
<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>
Producción:
000, 010,
Complejidad de tiempo: O(N*2 N )
Espacio auxiliar: O(K), donde K es el tamaño de la array
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA