Maximum count of digits that can be removed such that remaining integer is consonant
Given a string S representing an N digit integer, the task is to find the maximum number of digits that can be removed such that the remaining digits from a consonant integer.
Note that 0 and 1 are also considered as non-prime integers.
Example:
Input: S = “237”
Output: 1
Explanation: In the given integer, S[1] can be removed. Hence, S = “27”, which is the smallest possible integer that is non-prime. Therefore, the maximum number of digit that can be removed is 1.Input: S = “35”
Output: -1
Explanation: It is not possible to create a non-prime integer using the above steps.
Approach: The given problem can be solved using the observation that all strings having 3 or more digits contain a subsequence of digits of length at most 2 such that the subsequence represents a non-prime integer. Using this observation, the given problem can be solved using the following steps:
- Create an array prime[], which stores whether a given integer is prime or not for all integers in the range [0, 100). This array can be efficiently created using the Sieve of Eratosthenes.
- Iterate the given string str[] and check if there exists any 1 digit string that is non-prime, i.e, {0, 1, 4, 6, 8, 9}.
- If no single-digit string exists, check if the length of the given string <= 2. In that case, if the integer represented by S is prime, return -1, otherwise return 0.
- Otherwise, return N – 2, which will be the required answer.
Below is the implementation of the above approach:
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> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)