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 _
- Iterar un bucle desde j = 0 hasta la longitud de vec:
A continuación se muestra la implementación del enfoque anterior:
C++
// 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
# 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
Javascript
<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>
Producción:
3
Complejidad temporal : O(2 N * √N), donde N es la longitud de la string.
Espacio Auxiliar: O(2 N * N)
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA