Given a positive integer N and an array arr[] of size K consisting of binary string where each string is of size N, the task is to find all the binary strings of size N that are not present in the array arr[].
Examples:
Input: N = 3, arr[] = {“101”, “111”, “001”, “010”, “011”, “100”, “110”}
Output: 000
Explanation: Only 000 is absent in the given array.Input: N = 2, arr[] = {“00”, “01”}
Output: 10 11
Approach: The given problem can be solved by finding all binary strings of size N using Backtracking and then print those strings that are not present in the array arr[]. Follow the steps below to solve the problem:
- Initialize an unordered_set of strings S that stores all the strings in the array arr[].
- Initialize a variable, say total and set it as the power of 2N where N is the size of the string.
- Iterate over the range [0, total) using the variable i and perform the following steps:
- Initialize an empty string variable num as “”.
- Iterate over the range [N – 1, 0] using the variable j and if the value of the Bitwise AND of i and 2j is true, then push the character 1 into the string num. Otherwise, push the character 0.
- If num is not present in the set S then print the string num as the one of the resultant string.
- After completing the above steps, if all the possible binary strings are present in the array then print “-1”.
Below is the implementation of the above approach:
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 arrayvoid 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 Codeint main(){ int N = 3; vector<string> arr = { "101", "111", "001", "011", "100", "110" }; findMissingBinaryString(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find a Binary String of// same length other than the Strings// present in the arraystatic 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 Codepublic 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 approachfrom math import pow# Function to find a Binary String of# same length other than the Strings# present in the arraydef 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 Codeif __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 approachusing 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 arrayfunction 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 Codelet N = 3;let arr = ["101", "111", "001", "011", "100", "110"];findMissingBinaryString(arr, N);// This code is contributed by _saurabh_jaiswal.</script> |
Output:
000, 010,
Time Complexity: O(N*2N)
Auxiliary Space: O(K), where K is the size of the array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
