Dada la string numérica str , la tarea es contar el número de formas en que se puede dividir la string dada, de modo que cada segmento sea un número primo. Dado que la respuesta puede ser grande, devuelve la respuesta módulo 10 9 + 7 .
Nota : una división que contenga números con ceros a la izquierda no será válida y la string inicial no contiene ceros a la izquierda.
Ejemplos:
Entrada: str = “3175”
Salida: 3
Explicación:
Hay 3 formas de dividir esta string en números primos que son (31, 7, 5), (3, 17, 5), (317, 5).
Entrada: str = «11373»
Salida: 6
Explicación:
Hay 6 formas de dividir esta string en números primos que son (11, 3, 7, 3), (113, 7, 3), (11, 37, 3) , (11, 3, 73), (113, 73) y (11, 373).
Enfoque ingenuo: para resolver el problema mencionado anteriormente, el método ingenuo es usar Recursion .
- Comience recursivamente desde el índice final de la string dada y considere cada sufijo hasta 6 dígitos (dado que el número primo debe estar en el rango de [1, 10 6 )] y verifique si es un número primo o no.
- Si el sufijo no contiene un cero inicial y es un número primo, llame recursivamente a la función para contar las formas de la string restante y agregar al recuento total.
- Cuando el índice llega a 0, llegamos al caso base y devolvemos 1 para considerar las divisiones actuales como un recuento válido.
- Tome mod de la cuenta en cada iteración y devuelva la cuenta al final.
A continuación se muestra el enfoque de implementación anterior:
C++
// C++ implementation to count total
// number of ways to split a
// string to get prime numbers
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
// Function to check whether a number
// is a prime number or not
bool isPrime(string number)
{
int num = stoi(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return num > 1 ? true : false;
}
// Function to find the count
// of ways to split string
// into prime numbers
int countPrimeStrings(
string& number, int i)
{
// 1 based indexing
if (i == 0)
return 1;
int cnt = 0;
// Consider every suffix up to 6 digits
for (int j = 1; j <= 6; j++) {
// Number should not have
// a leading zero and
// it should be a prime number
if (i - j >= 0
&& number[i - j] != '0'
&& isPrime(
number.substr(i - j, j))) {
cnt
+= countPrimeStrings(
number,
i - j);
cnt %= MOD;
}
}
// Return the final result
return cnt;
}
// Driver code
int main()
{
string s1 = "3175";
int l = s1.length();
cout << countPrimeStrings(s1, l);
return 0;
}
Java
// Java implementation to count total
// number of ways to split a string
// to get prime numbers
import java.util.*;
class GFG{
static final int MOD =1000000007;
// Function to check whether a number
// is a prime number or not
static boolean isPrime(String number)
{
int num = Integer.valueOf(number);
for(int i = 2; i * i <= num; i++)
{
if ((num % i) == 0)
return false;
}
return num > 1 ? true : false;
}
// Function to find the count
// of ways to split String
// into prime numbers
static int countPrimeStrings(String number,
int i)
{
// 1 based indexing
if (i == 0)
return 1;
int cnt = 0;
// Consider every suffix up to 6 digits
for(int j = 1; j <= 6; j++)
{
// Number should not have
// a leading zero and it
// should be a prime number
if (i - j >= 0 &&
number.charAt(i - j) != '0' &&
isPrime(number.substring(i - j, i)))
{
cnt += countPrimeStrings(number,
i - j);
cnt %= MOD;
}
}
// Return the final result
return cnt;
}
// Driver code
public static void main(String[] args)
{
String s1 = "3175";
int l = s1.length();
System.out.print(countPrimeStrings(s1, l));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 implementation to # count total number of ways # to split a string to get # prime numbers MOD = 1000000007 # Function to check whether # a number is a prime number # or not def isPrime(number): num = int(number) i = 2 while i * i <= num: if ((num % i) == 0): return False i += 1 if num > 1: return True else: return False # Function to find the count # of ways to split string # into prime numbers def countPrimeStrings(number, i): # 1 based indexing if (i == 0): return 1 cnt = 0 # Consider every suffix # up to 6 digits for j in range(1, 7): # Number should not have # a leading zero and # it should be a prime number if (i - j >= 0 and number[i - j] != '0' and isPrime(number[i - j : i])): cnt += countPrimeStrings(number, i - j) cnt %= MOD # Return the final result return cnt # Driver code if __name__ == "__main__": s1 = "3175" l = len(s1) print (countPrimeStrings(s1, l)) # This code is contributed by Chitranayal
C#
// C# implementation to count total
// number of ways to split a string
// to get prime numbers
using System;
class GFG{
static readonly int MOD =1000000007;
// Function to check whether a number
// is a prime number or not
static bool isPrime(String number)
{
int num = Int32.Parse(number);
for(int i = 2; i * i <= num; i++)
{
if ((num % i) == 0)
return false;
}
return num > 1 ? true : false;
}
// Function to find the count
// of ways to split String
// into prime numbers
static int countPrimeStrings(String number,
int i)
{
// 1 based indexing
if (i == 0)
return 1;
int cnt = 0;
// Consider every suffix up to 6 digits
for(int j = 1; j <= 6; j++)
{
// Number should not have
// a leading zero and it
// should be a prime number
if (i - j >= 0 &&
number[i - j] != '0' &&
isPrime(number.Substring(i - j, j)))
{
cnt += countPrimeStrings(number,
i - j);
cnt %= MOD;
}
}
// Return the readonly result
return cnt;
}
// Driver code
public static void Main(String[] args)
{
String s1 = "3175";
int l = s1.Length;
Console.Write(countPrimeStrings(s1, l));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript implementation to count total
// number of ways to split a string
// to get prime numbers
let MOD =1000000007;
// Function to check whether a number
// is a prime number or not
function isPrime(number)
{
let num = parseInt(number);
for(let i = 2; i * i <= num; i++)
{
if ((num % i) == 0)
return false;
}
return num > 1 ? true : false;
}
// Function to find the count
// of ways to split String
// into prime numbers
function countPrimeStrings(number,i)
{
// 1 based indexing
if (i == 0)
return 1;
let cnt = 0;
// Consider every suffix up to 6 digits
for(let j = 1; j <= 6; j++)
{
// Number should not have
// a leading zero and it
// should be a prime number
if (i - j >= 0 &&
number[i - j] != '0' &&
isPrime(number.substring(i - j, i)))
{
cnt += countPrimeStrings(number,
i - j);
cnt %= MOD;
}
}
// Return the final result
return cnt;
}
// Driver code
let s1 = "3175";
let l = s1.length;
document.write(countPrimeStrings(s1, l));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad de tiempo: O(N 2 )
Espacio auxiliar: O(N)
Enfoque eficiente: Para optimizar el método anterior, la idea principal es usar la técnica de memorización para reducir la complejidad de tiempo de la solución recursiva discutida anteriormente. Consideremos una tabla dp[] que almacena en cada índice dp[i] , las formas de dividir los primeros i dígitos de la string str . La complejidad para comprobar si un número es primo o no puede reducirse aún más utilizando la criba de Eratóstenes .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count total
// number of ways to split a
// string to get prime numbers
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
bool sieve[1000000];
// Function to build sieve
void buildSieve()
{
for (auto& i : sieve)
i = true;
sieve[0] = false;
sieve[1] = false;
for (int p = 2; p * p <= 1000000;
p++) {
// If p is a prime
if (sieve[p] == true) {
// Update all multiples
// of p as non prime
for (int i = p * p; i <= 1000000;
i += p)
sieve[i] = false;
}
}
}
// Function to check whether a number
// is a prime number or not
bool isPrime(string number)
{
int num = stoi(number);
return sieve[num];
}
// Function to find the count
// of ways to split string
// into prime numbers
int rec(string& number, int i,
vector<int>& dp)
{
if (dp[i] != -1)
return dp[i];
int cnt = 0;
for (int j = 1; j <= 6; j++) {
// Number should not have a
// leading zero and it
// should be a prime number
if (i - j >= 0
&& number[i - j] != '0'
&& isPrime(
number.substr(i - j, j))) {
cnt += rec(
number, i - j, dp);
cnt %= MOD;
}
}
return dp[i] = cnt;
}
// Function to count the
// number of prime strings
int countPrimeStrings(string& number)
{
int n = number.length();
vector<int> dp(n + 1, -1);
dp[0] = 1;
return rec(number, n, dp);
}
// Driver code
int main()
{
buildSieve();
string s1 = "3175";
cout << countPrimeStrings(s1) << "\n";
return 0;
}
Java
// Java implementation to count total
// number of ways to split a String
// to get prime numbers
import java.util.*;
class GFG{
static int MOD = 1000000007;
static boolean []sieve = new boolean[1000000];
// Function to build sieve
static void buildSieve()
{
Arrays.fill(sieve, true);
sieve[0] = false;
sieve[1] = false;
for(int p = 2; p * p <= 1000000; p++)
{
// If p is a prime
if (sieve[p] == true)
{
// Update all multiples
// of p as non prime
for(int i = p * p; i < 1000000;
i += p)
sieve[i] = false;
}
}
}
// Function to check whether a number
// is a prime number or not
static boolean isPrime(String number)
{
int num = Integer.valueOf(number);
return sieve[num];
}
// Function to find the count
// of ways to split String
// into prime numbers
static int rec(String number, int i,
int []dp)
{
if (dp[i] != -1)
return dp[i];
int cnt = 0;
for(int j = 1; j <= 6; j++)
{
// Number should not have a
// leading zero and it
// should be a prime number
if (i - j >= 0 &&
number.charAt(i - j) != '0' &&
isPrime(number.substring(i - j, i)))
{
cnt += rec(number, i - j, dp);
cnt %= MOD;
}
}
return dp[i] = cnt;
}
// Function to count the
// number of prime Strings
static int countPrimeStrings(String number)
{
int n = number.length();
int []dp = new int[n + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
return rec(number, n, dp);
}
// Driver code
public static void main(String[] args)
{
buildSieve();
String s1 = "3175";
System.out.print(countPrimeStrings(s1) + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to count total # number of ways to split a String # to get prime numbers MOD = 1000000007 sieve = [0]*(1000000) # Function to build sieve def buildSieve(): for i in range(len(sieve)): sieve[i] = True sieve[0] = False sieve[1] = False p = 2 while p*p <= 1000000: # If p is a prime if sieve[p] == True: # Update all multiples # of p as non prime for i in range(p*p, 1000000, p): sieve[i] = False p+=1 # Function to check whether a number # is a prime number or not def isPrime(number): num = int(number) return sieve[num] # Function to find the count # of ways to split String # into prime numbers def rec(number,i,dp): if dp[i] != -1: return dp[i] cnt = 0 for j in range(1, 7): # Number should not have a # leading zero and it # should be a prime number if (i - j) >= 0 and number[i - j] != '0' and isPrime(number[i - j: i]): cnt += rec(number, i - j, dp) cnt %= MOD dp[i] = cnt return dp[i] # Function to count the # number of prime Strings def countPrimeStrings(number): n = len(number) dp = [0]*(n + 1) for i in range(n + 1): dp[i] = -1 dp[0] = 1 return rec(number, n, dp) # Driver code buildSieve() s1 = "3175" print(countPrimeStrings(s1)) # This code is contributed by suresh07.
C#
// C# implementation to count total
// number of ways to split a String
// to get prime numbers
using System;
class GFG{
static int MOD = 1000000007;
static bool []sieve = new bool[1000000];
// Function to build sieve
static void buildSieve()
{
for(int j = 0; j < sieve.Length; j++)
sieve[j] = true;
sieve[0] = false;
sieve[1] = false;
for(int p = 2; p * p <= 1000000; p++)
{
// If p is a prime
if (sieve[p] == true)
{
// Update all multiples
// of p as non prime
for(int i = p * p; i < 1000000;
i += p)
sieve[i] = false;
}
}
}
// Function to check whether a number
// is a prime number or not
static bool isPrime(String number)
{
int num = Int32.Parse(number);
return sieve[num];
}
// Function to find the count
// of ways to split String
// into prime numbers
static int rec(String number, int i,
int []dp)
{
if (dp[i] != -1)
return dp[i];
int cnt = 0;
for(int j = 1; j <= 6; j++)
{
// Number should not have a
// leading zero and it
// should be a prime number
if (i - j >= 0 &&
number[i - j] != '0' &&
isPrime(number.Substring(i - j, j)))
{
cnt += rec(number, i - j, dp);
cnt %= MOD;
}
}
return dp[i] = cnt;
}
// Function to count the
// number of prime Strings
static int countPrimeStrings(String number)
{
int n = number.Length;
int []dp = new int[n + 1];
for(int j = 0; j < dp.Length; j++)
dp[j] = -1;
dp[0] = 1;
return rec(number, n, dp);
}
// Driver code
public static void Main(String[] args)
{
buildSieve();
String s1 = "3175";
Console.Write(countPrimeStrings(s1) + "\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to count total
// number of ways to split a String
// to get prime numbers
let MOD = 1000000007;
let sieve = new Array(1000000);
// Function to build sieve
function buildSieve()
{
for(let i = 0; i < sieve.length; i++)
{
sieve[i] = true;
}
sieve[0] = false;
sieve[1] = false;
for(let p = 2; p * p <= 1000000; p++)
{
// If p is a prime
if (sieve[p] == true)
{
// Update all multiples
// of p as non prime
for(let i = p * p; i < 1000000;
i += p)
sieve[i] = false;
}
}
}
// Function to check whether a number
// is a prime number or not
function isPrime(number)
{
let num = parseInt(number);
return sieve[num];
}
// Function to find the count
// of ways to split String
// into prime numbers
function rec(number,i,dp)
{
if (dp[i] != -1)
return dp[i];
let cnt = 0;
for(let j = 1; j <= 6; j++)
{
// Number should not have a
// leading zero and it
// should be a prime number
if (i - j >= 0 &&
number[i - j] != '0' &&
isPrime(number.substring(i - j, i)))
{
cnt += rec(number, i - j, dp);
cnt %= MOD;
}
}
return dp[i] = cnt;
}
// Function to count the
// number of prime Strings
function countPrimeStrings(number)
{
let n = number.length;
let dp = new Array(n + 1);
for(let i = 0; i < (n + 1); i++)
{
dp[i] = -1;
}
dp[0] = 1;
return rec(number, n, dp);
}
// Driver code
buildSieve();
let s1 = "3175";
document.write(countPrimeStrings(s1) + "<br>");
// This code is contributed by rag2127
</script>
Producción:
3
Complejidad de tiempo: O(N + N*log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dabas_ajay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA