Número primo más grande posible de una subsecuencia de una string binaria

Dada una string binaria , la tarea es encontrar el número primo más grande posible mediante la representación decimal de una subsecuencia de la string binaria dada. Si no se puede obtener un número primo, imprima -1 .

Ejemplos:

Entrada: S = “1001”
Salida: 5 
Explicación: De todas las subsecuencias de la string “1001”, el mayor número primo que se puede obtener es “101” (= 5).

Entrada: “1011”
Salida: 11 
Explicación: De todas las subsecuencias de la string “1011”, el mayor número primo que se puede obtener es “1011” (= 11).

Enfoque:  Para resolver el problema, la idea es generar todas las subsecuencias posibles de la string y convertir cada subsecuencia a su forma decimal equivalente. Imprime el mayor número primo obtenido de estas subsucesiones. 

Siga los pasos a continuación para resolver este problema:

• Inicialice un vector de pares , digamos vec, para almacenar pares de strings y sus valores decimales equivalentes, en Pair.first y Pair.second respectivamente.
• Inicialice una variable, digamos ans, para almacenar la respuesta requerida.
• Iterar un bucle desde i = 0 hasta la longitud de la string s:
  • Iterar un bucle desde j = 0 hasta la longitud de vec:
    • Guarde el j ^-ésimo par en temp.
    • Si el i-ésimo carácter de la string s es ‘1 ‘:
      • Agregue el carácter en temp.first.
      • Actualice el valor de temp.second desplazando a la izquierda el valor actual y añadiéndole 1 .
    • De lo contrario:
      • Agregue el carácter en temp.first.
      • Actualice el valor de temp.second desplazando a la izquierda el valor actual y añadiéndole 0 .
    • Guarde este par temporal en vec .
    • Si el temp.second es primo :
      • Almacene max of ans y temp.second en ans .
  • Si ans es igual a 0 :
    • No se puede obtener ningún número primo de la string s .
  • De lo contrario:
    • Imprimir respuesta _

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
 
#include <iostream>
#include <vector>
using namespace std;
 
// Function to check if a
// number is prime or not
bool isPrime(int x)
{
    if (x <= 1)
        return false;
 
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0)
 
            // Return not prime
            return false;
    }
 
    // If prime return true
    return true;
}
 
// Function to find the largest prime
// number possible from a subsequence
void largestPrime(string s)
{
 
    // Stores pairs of subsequences and
    // their respective decimal value
    vector<pair<string, int> > vec{ { "", 0 } };
 
    // Stores the answer
    int ans = 0;
 
    // Traverse the string
    for (int i = 0; i < s.length(); i++) {
        // Stores the size of the vector
        int n = vec.size();
 
        // Traverse the vector
        for (int j = 0; j < n; j++) {
 
            // Extract the current pair
            pair<string, int> temp = vec[j];
 
            // Get the binary string from the pair
            string str = temp.first;
 
            // Stores equivalent decimal values
            int val = temp.second;
 
            // If the current character is '1'
            if (s[i] == '1') {
                // Add the character
                // to the subsequence
                temp.first = str + '1';
 
                // Update the value by left
                // shifting the current
                // value and adding 1 to it
                temp.second = ((val << 1) + 1);
            }
 
            // If s[i]=='0'
            else {
 
                // Add the character
                // to the subsequence
                temp.first = str + '0';
 
                // Update the value by left
                // shifting the current
                // value and adding 0 to it
                temp.second = ((val << 1) + 0);
            }
 
            // Store the subsequence in the vector
            vec.push_back(temp);
 
            // Check if the decimal
            // representation of current
            // subsequence is prime or not
            int check = temp.second;
 
            // If prime
            if (isPrime(check)) {
                // Update the answer
                // with the largest one
                ans = max(ans, check);
            }
        }
    }
 
    // If no prime number
    // could be obtained
    if (ans == 0)
        cout << -1 << endl;
    else
        cout << ans << endl;
}
 
// Driver Code
int main()
{
    // Input String
    string s = "110";
 
    largestPrime(s);
 
    return 0;
}

# Python3 program to implement
# the above approach
 
# Function to check if a
# number is prime or not
def isPrime(x):
     
    if (x <= 1):
        return False
 
    for i in range(2, x + 1):
        if i * i > x:
            break
         
        if (x % i == 0):
             
            # Return not prime
            return False
 
    # If prime return true
    return True
 
# Function to find the largest prime
# number possible from a subsequence
def largestPrime(s):
 
    # Stores pairs of subsequences and
    # their respective decimal value
    vec = [["", 0]]
     
    # Stores the answer
    ans = 0
 
    # Traverse the string
    for i in range(len(s)):
         
        # Stores the size of the vector
        n = len(vec)
 
        # Traverse the vector
        for j in range(n):
             
            # Extract the current pair
            temp = vec[j]
 
            # Get the binary string from the pair
            str = temp[0]
 
            # Stores equivalent decimal values
            val = temp[1]
 
            # If the current character is '1'
            if (s[i] == '1'):
                 
                # Add the character
                # to the subsequence
                temp[0] = str + '1'
 
                # Update the value by left
                # shifting the current
                # value and adding 1 to it
                temp[1] = ((val << 1) + 1)
 
            # If s[i]=='0'
            else:
 
                # Add the character
                # to the subsequence
                temp[0] = str + '0'
 
                # Update the value by left
                # shifting the current
                # value and adding 0 to it
                temp[1] = ((val << 1) + 0)
 
            # Store the subsequence in the vector
            vec.append(temp)
 
            # Check if the decimal
            # representation of current
            # subsequence is prime or not
            check = temp[1]
 
            # If prime
            if (isPrime(check)):
                 
                # Update the answer
                # with the largest one
                ans = max(ans, check)
                break
 
    # If no prime number
    # could be obtained
    if (ans == 0):
        print(-1)
    else:
        print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    # Input String
    s = "110"
 
    largestPrime(s)
 
# This code is contributed by mohit kumar 29

<script>
 
// JavaScript Program to implement
// the above approach
 
// Function to check if a
// number is prime or not
function isPrime(x) {
    if (x <= 1)
        return false;
 
    for (let i = 2; i * i <= x; i++) {
        if(i * i > x){
            break
        }
        if (x % i == 0)
 
            // Return not prime
            return false;
    }
 
    // If prime return true
    return true;
}
 
// Function to find the largest prime
// number possible from a subsequence
function largestPrime(s) {
 
    // Stores pairs of subsequences and
    // their respective decimal value
    let vec = [["", 0]];
 
    // Stores the answer
    let ans = 0;
 
    // Traverse the string
    for (let i = 0; i < s.length; i++) {
        // Stores the size of the vector
        let n = vec.length;
 
        // Traverse the vector
        for (let j = 0; j < n; j++) {
 
            // Extract the current pair
            let temp = vec[j];
 
            // Get the binary string from the pair
            let str = temp[0];
 
            // Stores equivalent decimal values
            let val = temp[1];
 
            // If the current character is '1'
            if (s[i] == '1') {
                // Add the character
                // to the subsequence
                temp[0] = str + '1';
 
                // Update the value by left
                // shifting the current
                // value and adding 1 to it
                temp[1] = ((val << 1) + 1);
            }
 
            // If s[i]=='0'
            else {
 
                // Add the character
                // to the subsequence
                temp[0] = str + '0';
 
                // Update the value by left
                // shifting the current
                // value and adding 0 to it
                temp[1] = ((val << 1) + 0);
            }
 
            // Store the subsequence in the vector
            vec.push(temp);
 
            // Check if the decimal
            // representation of current
            // subsequence is prime or not
            let check = temp[1];
 
            // If prime
            if (isPrime(check)) {
                // Update the answer
                // with the largest one
                ans = Math.max(ans, check);
                break
            }
        }
    }
 
    // If no prime number
    // could be obtained
    if (ans == 0)
        document.write(-1 + "<br>");
    else
        document.write(ans + "<br>");
}
 
// Driver Code
 
// Input String
let s = "110";
 
largestPrime(s);
 
</script>

3

Complejidad temporal : O(2 ^N * √N), donde N es la longitud de la string.
Espacio Auxiliar: O(2 ^N * N)