Número mínimo cuya forma binaria no es una subsecuencia de una string binaria dada

Dada una string binaria S de tamaño N , la tarea es encontrar el número entero mínimo no negativo que no sea una subsecuencia de la string S dada en su forma binaria .

Ejemplos:

Entrada: S = “0000”
Salida: 1
Explicación:  1 cuya representación binaria es “1” es el entero no negativo más pequeño que no es una subsecuencia de la string dada en su forma binaria. 

Entrada: S = “10101”
Salida: 8

Enfoque: La idea es convertir la string dada en su representación decimal , digamos R. Luego, itere en el rango [0, R] para verificar si cada número entero existe o no como una subsecuencia en su forma binaria en la string dada, S . De lo contrario, rompa el ciclo e imprima el resultado requerido. 
Siga los pasos a continuación para resolver el problema:

• Almacene el número decimal de la string binaria , S en una variable R.
• Inicialice una variable ans como R+1 para almacenar el resultado requerido.
• Iterar en el rango [0, R] usando la variable i
  • Convierta el entero i dado en su string binaria y guárdelo en la string P .
  • Compruebe si la string P es una subsecuencia de la string S o no . Si no es así, actualice ans a i y salga del ciclo .
• Imprime el valor de ans como resultado.

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

# 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# 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.

8

Complejidad de tiempo: O(N*R), donde R es la representación decimal de la string binaria dada, S
Espacio auxiliar: O(N)