Minimum number whose binary form is not a subsequence of given binary string

0 0 7 minutes read

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 str2
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
void 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 Code
int main()
{
 
    // Function Call
    string s = "10101";
 
    // Function Call
    findMinimumNumber(s);
 
    return 0;
}

Java

// Java program for the above approach
import 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 str2
def 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 form
def 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 Code
if __name__ == '__main__':
   
    # Function Call
    s = "10101"
     
    # Function Call
    findMinimumNumber(s)
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program for the above approach
using 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 str2
function 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 form
function 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

Time Complexity: O(N*R), where R is the decimal representation of the given binary string, S
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!