Given a binary string S of size N, the task is to find the minimum non-negative integer which is not a subsequence of the given string S in its binary form.
Examples:
Input: S = “0000”
Output:1
Explanation: 1 whose binary representation is “1” is the smallest non-negative integer which is not a subsequence of the given string in its binary form.Input: S = “10101”
Output: 8
Approach: The idea is to convert the given string into its decimal representation, say R. Then iterate in the range [0, R] to check for each integer whether it exists or not as a subsequence in its binary form in the given string, S. If not, then break the loop and print the required result.
Follow the steps below to solve the problem:
- Store the decimal number of the binary string, S in a variable R.
- Initialize a variable ans as R+1 to store the required result.
- Iterate in the range [0, R] using the variable i
- Convert the given integer i into its binary string, and store it in string P.
- Check if string P is a subsequence of string S or not. If it is not, then update ans to i and break out of the loop.
- Print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if string str1 is a// subsequence of string str2bool isSubsequence(string str1, string str2, int m, int n){ // Store index of str1 int j = 0; // Traverse str2 and str1, and compare // current character of str2 with first // unmatched char of str1 for (int i = 0; i < n && j < m; i++) // If matched, move ahead in str1 if (str1[j] == str2[i]) j++; // If all characters of str1 were // found in str2 return (j == m);}// Function to find the minimum number which // is not a subsequence of the given binary // string in its binary formvoid findMinimumNumber(string s){ // Store the decimal number of string, S int r = stoi(s, 0, 2); // Initialize the required result int ans = r + 1; // Iterate in the range [0, R] for (int i = 0; i <= r; i++) { // Convert integer i to binary string string p = ""; int j = i; while (j > 0) { p += to_string(j % 2); j = j / 2; } int m = p.length(); int n = s.length(); reverse(p.begin(), p.end()); // Check if the string is not a subsequence if (!isSubsequence(p, s, m, n)) { // Update ans and break ans = i; break; } } // Print the required result cout << ans;}// Driver Codeint main(){ // Function Call string s = "10101"; // Function Call findMinimumNumber(s); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to check if string str1 is a // subsequence of string str2 static boolean isSubsequence(String str1, String str2, int m, int n) { // Store index of str1 int j = 0; // Traverse str2 and str1, and compare // current character of str2 with first // unmatched char of str1 for (int i = 0; i < n && j < m; i++) // If matched, move ahead in str1 if (str1.charAt(j) == str2.charAt(i)) j++; // If all characters of str1 were found // in str2 return (j == m); } // Function to find the minimum number which // is not a subsequence of the given binary // string in its binary form static void findMinimumNumber(String s) { // Store the decimal number of string, S int r = Integer.parseInt(s, 2); // Initialize the required result int ans = r + 1; // Iterate in the range [0, R] for (int i = 0; i <= r; i++) { // Convert integer i to binary string String p = ""; int j = i; while (j > 0) { p += (j % 2) + ""; j = j / 2; } int m = p.length(); int n = s.length(); StringBuilder sb = new StringBuilder(p); sb.reverse(); p = sb.toString(); // Check if the string is not a subsequence if (!isSubsequence(p, s, m, n)) { // Update ans and break ans = i; break; } } // Print the required result System.out.println(ans); } // Driver Code public static void main(String[] args) { // Function Call String s = "10101"; // Function Call findMinimumNumber(s); }}// This code is contributed by Karandeep1234 |
Python3
# python 3 program for the above approach# Function to check if string str1 is a# subsequence of string str2def isSubsequence(str1, str2, m, n): # Store index of str1 j = 0 # Traverse str2 and str1, and compare # current character of str2 with first # unmatched char of str1 i = 0 while(i < n and j < m): # If matched, move ahead in str1 if (str1[j] == str2[i]): j += 1 i += 1 # If all characters of str1 were # found in str2 return (j == m)# Function to find the minimum number which # is not a subsequence of the given binary # string in its binary formdef findMinimumNumber(s): # Store the decimal number of string, S r = int(s,2) # Initialize the required result ans = r + 1 # Iterate in the range [0, R] for i in range(r+1): # Convert integer i to binary string p = "" j = i while (j > 0): p += str(j % 2) j = j // 2 m = len(p) n = len(s) p = p[::-1] # Check if the string is not a subsequence if (isSubsequence(p, s, m, n) == False): # Update ans and break ans = i break # Print the required result print(ans)# Driver Codeif __name__ == '__main__': # Function Call s = "10101" # Function Call findMinimumNumber(s) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG { // Function to check if string str1 is a // subsequence of string str2 static bool isSubsequence(string str1, string str2, int m, int n) { // Store index of str1 int j = 0; // Traverse str2 and str1, and compare // current character of str2 with first // unmatched char of str1 for (int i = 0; i < n && j < m; i++) // If matched, move ahead in str1 if (str1[j] == str2[i]) j++; // If all characters of str1 were // found in str2 return (j == m); } // Function to find the minimum number which // is not a subsequence of the given binary // string in its binary form static void findMinimumNumber(string s) { // Store the decimal number of string, S int r = Int32.Parse(s); // Initialize the required result int ans = r + 1; // Iterate in the range [0, R] for (int i = 0; i <= r; i++) { // Convert integer i to binary string string p = ""; int j = i; while (j > 0) { p += (j % 2).ToString(); j = j / 2; } int m = p.Length; int n = s.Length; char[] stringArray = p.ToCharArray(); Array.Reverse(stringArray); p = new string(stringArray); // Check if the string is not a subsequence if (!isSubsequence(p, s, m, n)) { // Update ans and break ans = i; break; } } // Print the required result Console.WriteLine(ans); } // Driver Code public static void Main() { // Function Call string s = "10101"; // Function Call findMinimumNumber(s); }}// This code is contributed by ukasp. |
Javascript
// JavaScript implementation of the above approach// Function to check if string str1 is a// subsequence of string str2function isSubsequence(str1, str2, m, n){ // Store index of str1 let j = 0; // Traverse str2 and str1, and compare // current character of str2 with first // unmatched char of str1 let i = 0; while (i < n && j < m) { // If matched, move ahead in str1 if (str1[j] == str2[i]) { j++; } i++; } // If all characters of str1 were // found in str2 return j == m;}// Function to find the minimum number which// is not a subsequence of the given binary// string in its binary formfunction findMinimumNumber(s){ // Store the decimal number of string, S let r = parseInt(s, 2); // Initialize the required result let ans = r + 1; // Iterate in the range [0, R] for (let i = 0; i <= r; i++) { // Convert integer i to binary string let p = ""; let j = i; while (j > 0) { p += j % 2; j = Math.floor(j / 2); } let m = p.length; let n = s.length; p = p.split("").reverse().join(""); // Check if the string is not a subsequence if (isSubsequence(p, s, m, n) == false) { // Update ans and break ans = i; break; } } // Print the required result console.log(ans);}// Driver Code(function main() { // Function Call let s = "10101"; // Function Call findMinimumNumber(s);})();// This code is contributed by phasing17 |
Output
8
Time Complexity: O(N*R), where R is the decimal representation of the given binary string, S
Auxiliary Space: O(N)
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!
