Dada una string S que representa un número entero de N dígitos, la tarea es encontrar el número máximo de dígitos que se pueden eliminar de tal manera que los dígitos restantes de un número entero consonante.
Tenga en cuenta que 0 y 1 también se consideran números enteros no primos.
Ejemplo:
Entrada: S = “237”
Salida: 1
Explicación: En el entero dado, S[1] puede eliminarse. Por lo tanto, S = «27», que es el número entero más pequeño posible que no es primo. Por lo tanto, el número máximo de dígitos que se pueden eliminar es 1.Entrada: S = “35”
Salida: -1
Explicación: No es posible crear un número entero no primo usando los pasos anteriores.
Enfoque: El problema dado se puede resolver utilizando la observación de que todas las strings que tienen 3 o más dígitos contienen una subsecuencia de dígitos de longitud máxima de 2 , de modo que la subsecuencia representa un número entero no primo. Usando esta observación, el problema dado se puede resolver usando los siguientes pasos:
- Cree una array prime[] , que almacene si un entero dado es primo o no para todos los enteros en el rango [0, 100) . Esta array se puede crear de manera eficiente utilizando el tamiz de Eratóstenes .
- Itere la string dada str[] y verifique si existe alguna string de 1 dígito que no sea primo, es decir, {0, 1, 4, 6, 8, 9} .
- Si no existe una string de un solo dígito, verifique si la longitud de la string dada <= 2 . En ese caso, si el número entero representado por S es primo, devuelve -1 , de lo contrario, devuelve 0 .
- De lo contrario, devuelva N – 2 , que será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores if integer representing
// the index is prime of not
bool prime[100];
// Function to calculate prime[]
// using sieve of eratosthenes
void sieve()
{
// Set all integers as prime
for (int i = 0; i < 100; i++) {
prime[i] = true;
}
// Since 0 and 1 are considered
// as the non prime integers
prime[0] = false;
prime[1] = false;
for (int i = 2; i < 100; i++) {
if (!prime[i])
continue;
for (int j = 2 * i; j < 100; j += i) {
prime[j] = false;
}
}
}
// Function to find the maximum count of
// digits that can be removed such that
// the remaining integer is non-prime
int maxCount(string S)
{
// Loop to iterate over all
// digits in string S
for (int i = 0; i < S.size(); i++) {
// If a non-prime single
// digit integer is found
if (!prime[S[i] - '0']) {
return S.length() - 1;
}
}
// If the length of string
// is at most 2
if (S.length() <= 2) {
// If S represents a
// prime integer
if (prime[stoi(S)])
return -1;
else
return 0;
}
else {
// Return Answer
return S.length() - 2;
}
}
// Driver Code
int main()
{
string S = "237";
sieve();
cout << maxCount(S);
return 0;
}
Java
// JAVA program of the above approach
import java.util.*;
class GFG
{
// Stores if integer representing
// the index is prime of not
private static boolean[] prime = new boolean[100];
// Function to calculate prime[]
// using sieve of eratosthenes
public static void sieve()
{
// Set all integers as prime
for (int i = 0; i < 100; i++) {
prime[i] = true;
}
// Since 0 and 1 are considered
// as the non prime integers
prime[0] = false;
prime[1] = false;
for (int i = 2; i < 100; i++) {
if (!prime[i])
continue;
for (int j = 2 * i; j < 100; j += i) {
prime[j] = false;
}
}
}
// Function to find the maximum count of
// digits that can be removed such that
// the remaining integer is non-prime
public static int maxCount(String S)
{
// Loop to iterate over all
// digits in string S
for (int i = 0; i < S.length(); i++)
{
// If a non-prime single
// digit integer is found
if (!prime[S.charAt(i) - '0']) {
return S.length() - 1;
}
}
// If the length of string
// is at most 2
if (S.length() <= 2) {
// If S represents a
// prime integer
if (prime[Integer.parseInt(S)])
return -1;
else
return 0;
}
else {
// Return Answer
return S.length() - 2;
}
}
// Driver Code
public static void main(String[] args)
{
String S = "237";
sieve();
System.out.print(maxCount(S));
}
}
// This code is contributed by Taranpreet
Python3
# Stores if integer representing # the index is prime of not prime = [] # Function to calculate prime[] # using sieve of eratosthenes def sieve(): # Set all integers as prime for i in range(100): prime.append(True) # Since 0 and 1 are considered # as the non prime integers prime[0] = False prime[1] = False for i in range(2, 100): if (not prime[i]): continue for j in range(2*i, 100, i): prime[j] = False # Function to find the maximum count of # digits that can be removed such that # the remaining integer is non-prime def maxCount(S): # Loop to iterate over all # digits in string S N = len(S) for i in range(N): # If a non-prime single # digit integer is found if (not prime[int(S[i])]): return N - 1 # If the length of string # is at most 2 if (N <= 2): # If S represents a # prime integer if (prime[int(S)]): return -1 else: return 0 else: # Return Answer return N - 2 # driver code S = "237" sieve() print(maxCount(S)) # This code is contributed by Palak Gupta
C#
using System;
public class GFG
{
// Stores if integer representing
// the index is prime of not
private static bool[] prime = new bool[100];
// Function to calculate prime[]
// using sieve of eratosthenes
public static void sieve()
{
// Set all integers as prime
for (int i = 0; i < 100; i++) {
prime[i] = true;
}
// Since 0 and 1 are considered
// as the non prime integers
prime[0] = false;
prime[1] = false;
for (int i = 2; i < 100; i++) {
if (!prime[i])
continue;
for (int j = 2 * i; j < 100; j += i) {
prime[j] = false;
}
}
}
// Function to find the maximum count of
// digits that can be removed such that
// the remaining integer is non-prime
public static int maxCount(string S)
{
// Loop to iterate over all
// digits in string S
for (int i = 0; i < S.Length; i++)
{
// If a non-prime single
// digit integer is found
if (!prime[S[i] - '0']) {
return S.Length - 1;
}
}
// If the length of string
// is at most 2
if (S.Length <= 2) {
// If S represents a
// prime integer
if (prime[Int32.Parse(S)])
return -1;
else
return 0;
}
else {
// Return Answer
return S.Length - 2;
}
}
// Driver code
static public void Main (){
string S = "237";
sieve();
Console.Write(maxCount(S));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code for the above approach
// Stores if integer representing
// the index is prime of not
let prime = new Array(100);
// Function to calculate prime[]
// using sieve of eratosthenes
function sieve()
{
// Set all integers as prime
for (let i = 0; i < 100; i++) {
prime[i] = true;
}
// Since 0 and 1 are considered
// as the non prime integers
prime[0] = false;
prime[1] = false;
for (let i = 2; i < 100; i++) {
if (!prime[i])
continue;
for (let j = 2 * i; j < 100; j += i) {
prime[j] = false;
}
}
}
// Function to find the maximum count of
// digits that can be removed such that
// the remaining integer is non-prime
function maxCount(S)
{
// Loop to iterate over all
// digits in string S
for (let i = 0; i < S.length; i++)
{
// If a non-prime single
// digit integer is found
if (!prime[S[i].charCodeAt(0) - '0'.charCodeAt(0)]) {
return S.length - 1;
}
}
// If the length of string
// is at most 2
if (S.length <= 2) {
// If S represents a
// prime integer
if (prime[parseInt(S)])
return -1;
else
return 0;
}
else {
// Return Answer
return S.length - 2;
}
}
// Driver Code
let S = "237";
sieve();
document.write(maxCount(S));
// This code is contributed by Potta Lokesh
</script>
Producción
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA