Dada una string S de tamaño N que consta de dígitos [1, 9] , la tarea es encontrar la longitud de la subsecuencia más pequeña en la string tal que no sea un número primo .
Ejemplos:
Entrada: S = “237”
Salida: 2
Explicación:
Hay 7 subsecuencias no vacías {“2”, “3”, “7”, “23”, “27”, “37”, “237”}. Entre estas subsecuencias hay dos subsecuencias que no son primos, es decir, 27 y 237. Por lo tanto, como 27 tiene una longitud de 2, imprima 2.Entrada: S = “44444”
Salida: 1
Planteamiento: La idea para resolver este problema se basa en la observación de que si al eliminar j o más de j caracteres de la string S la string es un número primo , entonces la respuesta debe ser mayor que j . Con base en este hecho, forme todas las strings de modo que al eliminar un elemento de esa string se obtenga un número primo. Todas las strings posibles de la intuición anterior son {2, 3, 5, 7, 23, 37, 53, 73} Por lo tanto, el tamaño máximo posible de la subsecuencia es 3 . Por lo tanto, la idea es atravesar todas las subsecuencias de tamaño 1 y tamaño 2 y si se encuentra que las subsecuencias contienenal menos 1 elemento que no está presente en la lista , entonces el tamaño podría ser 1 o 2 . De lo contrario, el tamaño será 3 . Siga los pasos a continuación para resolver el problema:
- Inicialice el indicador de variable booleana como falso.
- Inicializa un ficticio de string vacía .
- Itere sobre el rango [0, N) usando la variable j y realice las siguientes tareas:
- Si el carácter en la posición j-ésima no es igual a 2 o 3 o 5 o 7, imprima la respuesta como 1, establezca el valor de la bandera como verdadero y rompa.
- Si el indicador es verdadero , de lo contrario, realice las siguientes tareas.
- Itere sobre el rango [0, N) usando la variable j y realice las siguientes tareas:
- Iterar sobre el rango [j+1, N) usando la variable j1 y realizar las siguientes tareas:
- Cree una string ficticia con caracteres en la posición j y j1 .
- Si la string ficticia no es igual a 2, 3, 5, 7, 23, 37, 53 y 73 , imprima la respuesta como 2 y establezca el valor de la bandera como verdadero y rompa .
- Iterar sobre el rango [j+1, N) usando la variable j1 y realizar las siguientes tareas:
- Si la bandera es falsa y la longitud de la string S es mayor que igual a 3 , imprima 3 como respuesta, de lo contrario imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest
// length of resultant subsequence
void findMinimumSubsequence(
string S)
{
bool flag = false;
string dummy;
// Check for a subsequence of size 1
for (int j = 0; j < S.length(); j++)
{
if (S[j] != '2' && S[j] != '3' && S[j] != '5' && S[j] != '7')
{
cout << 1;
flag = true;
break;
}
}
// Check for a subsequence of size 2
if (!flag)
{
for (int j = 0;
j < S.length() - 1; j++)
{
for (int j1 = j + 1;
j1 < S.length(); j1++)
{
dummy = S[j] + S[j1];
if (dummy != "23" && dummy != "37" && dummy != "53" && dummy != "73")
{
cout << 2;
}
if (flag = true)
break;
}
if (flag = true)
break;
}
}
// If none of the above check is
// successful then subsequence
// must be of size 3
if (!flag)
{
if (S.length() >= 3)
{
// Never executed
cout << 3;
}
else
{
cout << -1;
}
}
}
// Driver Code
int main()
{
string S = "237";
findMinimumSubsequence(S);
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the smallest
// length of resultant subsequence
public static void findMinimumSubsequence(
String S)
{
boolean flag = false;
StringBuilder dummy = new StringBuilder();
// Check for a subsequence of size 1
for (int j = 0; j < S.length(); j++) {
if (S.charAt(j) != '2' && S.charAt(j) != '3'
&& S.charAt(j) != '5'
&& S.charAt(j) != '7') {
System.out.println(1);
flag = true;
break;
}
}
// Check for a subsequence of size 2
if (!flag) {
loop:
for (int j = 0;
j < S.length() - 1; j++) {
for (int j1 = j + 1;
j1 < S.length(); j1++) {
dummy = new StringBuilder(
Character.toString(S.charAt(j)));
dummy.append(S.charAt(j1));
if (!dummy.toString().equals("23")
&& !dummy.toString().equals("37")
&& !dummy.toString().equals("53")
&& !dummy.toString().equals("73")) {
System.out.println(2);
flag = true;
break loop;
}
}
}
}
// If none of the above check is
// successful then subsequence
// must be of size 3
if (!flag) {
if (S.length() >= 3) {
// Never executed
System.out.println(3);
}
else {
System.out.println(-1);
}
}
}
// Driver Code
public static void main(String[] args)
{
String S = "237";
findMinimumSubsequence(S);
}
}
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the smallest
// length of resultant subsequence
static void findMinimumSubsequence(string S)
{
bool flag = false;
string dummy = "";
// Check for a subsequence of size 1
for (int j = 0; j < S.Length; j++) {
if (S[j] != '2' && S[j] != '3' && S[j] != '5'
&& S[j] != '7') {
Console.WriteLine(1);
flag = true;
break;
}
}
// Check for a subsequence of size 2
if (!flag) {
for (int j = 0; j < S.Length - 1; j++) {
for (int j1 = j + 1; j1 < S.Length; j1++) {
dummy = S[j].ToString()
+ S[j1].ToString();
if (dummy != "23" && dummy != "37"
&& dummy != "53" && dummy != "73") {
Console.WriteLine(2);
}
if (flag == true)
break;
else
flag = true;
}
if (flag == true)
break;
}
}
// If none of the above check is
// successful then subsequence
// must be of size 3
if (flag == false) {
if (S.Length >= 3) {
// Never executed
Console.WriteLine(3);
}
else {
Console.WriteLine(-1);
}
}
}
// Driver Code
public static void Main()
{
string S = "237";
findMinimumSubsequence(S);
}
}
// This code is contributed by ukasp.
Python3
# Python 3 program for the above approach # Function to find the smallest # length of resultant subsequence def findMinimumSubsequence(S): flag = False dummy = '' # Check for a subsequence of size 1 for j in range(len(S)): if (S[j] != '2' and S[j] != '3' and S[j] != '5' and S[j] != '7'): print(1) flag = True break # Check for a subsequence of size 2 if (flag == False): for j in range(len(S)): for j1 in range(j + 1,len(S),1): dummy = S[j] + S[j1] if (dummy != "23" and dummy != "37" and dummy != "53" and dummy != "73"): print(2) if (flag == True): break else: flag = True if (flag == True): break # If none of the above check is # successful then subsequence # must be of size 3 if (flag == False): if (len(S) >= 3): # Never executed print(3) else: print(-1) # Driver Code if __name__ == '__main__': S = "237" findMinimumSubsequence(S) # This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the smallest
// length of resultant subsequence
function findMinimumSubsequence(S)
{
let flag = false;
// Check for a subsequence of size 1
for (let j = 0; j < S.length; j++)
{
if (S[j] != '2' && S[j] != '3' && S[j] != '5' && S[j] != '7')
{
document.write(1);
flag = true;
break;
}
}
// Check for a subsequence of size 2
if (flag == false)
{
for (let j = 0; j < S.length; j++)
{
for (let j1 = j + 1; j1 < S.length; j1++)
{
let dummy = S[j] + S[j1];
if (dummy != "23" && dummy != "37" && dummy != "53" && dummy != "73")
{
document.write(2);
}
if (flag == true)
break;
else
flag = true;
}
if (flag == true)
break;
}
}
// If none of the above check is
// successful then subsequence
// must be of size 3
if (flag == false)
{
if (S.length >= 3)
{
// Never executed
document.write(3);
}
else
{
document.write(-1);
}
}
}
// Driver Code
let S = "237";
findMinimumSubsequence(S);
// This code is contributed by AnkThon
</script>
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por debarpan_bose_chowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA