Dado un número en forma de string s , la tarea es calcular y mostrar las divisiones mínimas requeridas de modo que los segmentos formados sean Prime o imprima No es posible de otra manera.
Ejemplos:
Entrada: s = “2351”
Salida: 0
Explicación: El número dado ya es primo.
Entrada: s = “2352”
Salida: 2
Explicación: Los segmentos primos resultantes son 23,5,2
Entrada: s = “2375672”
Salida: 2
Explicación: Los segmentos primos resultantes son 2,37567,2
Enfoque:
Este problema es una variación de Matrix Chain Multiplication y se puede resolver usando programación dinámica .
Pruebe todas las divisiones posibles recursivamente y en cada división, verifique si los segmentos formados son primos o no. Considere una array 2D dp donde dp[i][j] muestra las divisiones mínimas del índice i al j y devuelve dp[0][n] donde n es la longitud de la string.
Recurrencia :
dp[i][j] = min(1 + solve(i, k) + solve(k + 1, j)) where i <= k <= j
En realidad, en la recurrencia exacta escrita arriba, los segmentos izquierdo y derecho no son primos , entonces 1 + INT_MAX + INT_MAX será negativo , lo que conduce a una respuesta incorrecta.
Por lo tanto, se requieren cálculos separados para los segmentos izquierdo y derecho . Si se encuentra que algún segmento no es primo, no es necesario continuar. Devuelve min(1+left+right) de lo contrario.
Los casos base considerados son:
- Si el número es primo, devuelve 0
- Si i==j y el número es primo, devuelve 0
- Si i==j y el número no es primo, devuelve INT_MAX
El siguiente código es la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int dp[1000][1000] = { 0 };
// Checking for prime
bool isprime(long long num)
{
if (num <= 1)
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Conversion of string to int
long long convert(string s, int i, int j)
{
long long temp = 0;
for (int k = i; k <= j; k++) {
temp = temp * 10 + (s[k] - '0');
}
return temp;
}
// Function to get the minimum splits
int solve(string s, int i, int j)
{
// Convert the segment to integer or long long
long long num = convert(s, i, j);
// Number is prime
if (isprime(num)) {
return 0;
}
// If a single digit is prime
if (i == j && isprime(num))
return 0;
// If single digit is not prime
if (i == j && isprime(num) == false)
return INT_MAX;
if (dp[i][j])
return dp[i][j];
int ans = INT_MAX;
for (int k = i; k < j; k++) {
// Recur for left segment
int left = solve(s, i, k);
if (left == INT_MAX) {
continue;
}
// Recur for right segment
int right = solve(s, k + 1, j);
if (right == INT_MAX) {
continue;
}
// Minimum from left and right segment
ans = min(ans, 1 + left + right);
}
return dp[i][j] = ans;
}
int main()
{
string s = "2352";
int n = s.length();
int cuts = solve(s, 0, n - 1);
if (cuts != INT_MAX) {
cout << cuts;
}
else {
cout << "Not Possible";
}
}
Java
import java.util.*;
class GFG
{
static int dp[][] = new int[1000][1000];
// Checking for prime
static boolean isprime(long num){
int i;
if (num <= 1)
return false;
for (i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Conversion of string to int
static long convert(String s, int i, int j)
{
long temp = 0;
int k;
for (k = i; k <= j; k++) {
temp = temp * 10 + (s.charAt(k) - '0');
}
return temp;
}
// Function to get the minimum splits
static int solve(String s, int i, int j)
{
int k;
// Convert the segment to integer or long long
long num = convert(s, i, j);
// Number is prime
if (isprime(num)) {
return 0;
}
// If a single digit is prime
if (i == j && isprime(num))
return 0;
// If single digit is not prime
if (i == j && isprime(num) == false)
return Integer.MAX_VALUE;
if (dp[i][j] != 0)
return dp[i][j];
int ans = Integer.MAX_VALUE;
for (k = i; k < j; k++) {
// Recur for left segment
int left = solve(s, i, k);
if (left == Integer.MAX_VALUE) {
continue;
}
// Recur for right segment
int right = solve(s, k + 1, j);
if (right == Integer.MAX_VALUE) {
continue;
}
// Minimum from left and right segment
ans = Math.min(ans, 1 + left + right);
}
return dp[i][j] = ans;
}
public static void main (String []args)
{
String s = "2352";
int n = s.length();
int cuts = solve(s, 0, n - 1);
if (cuts != Integer.MAX_VALUE) {
System.out.print(cuts);
}
else {
System.out.print("Not Possible");
}
}
}
// This code is contributed by chitranayal
Python3
# Python3 Implementation of the above approach
import numpy as np;
import sys
dp = np.zeros((1000,1000)) ;
INT_MAX = sys.maxsize;
# Checking for prime
def isprime(num) :
if (num <= 1) :
return False;
for i in range(2, int(num ** (1/2)) + 1) :
if (num % i == 0) :
return False;
return True;
# Conversion of string to int
def convert(s, i, j) :
temp = 0;
for k in range(i, j + 1) :
temp = temp * 10 + (ord(s[k]) - ord('0'));
return temp;
# Function to get the minimum splits
def solve(s, i, j) :
# Convert the segment to integer or long long
num = convert(s, i, j);
# Number is prime
if (isprime(num)) :
return 0;
# If a single digit is prime
if (i == j and isprime(num)) :
return 0;
# If single digit is not prime
if (i == j and isprime(num) == False) :
return INT_MAX;
if (dp[i][j]) :
return dp[i][j];
ans = INT_MAX;
for k in range(i, j) :
# Recur for left segment
left = solve(s, i, k);
if (left == INT_MAX) :
continue;
# Recur for right segment
right = solve(s, k + 1, j);
if (right == INT_MAX) :
continue;
# Minimum from left and right segment
ans = min(ans, 1 + left + right);
dp[i][j] = ans;
return ans;
# Driver code
if __name__ == "__main__" :
s = "2352";
n = len(s);
cuts = solve(s, 0, n - 1);
if (cuts != INT_MAX) :
print(cuts);
else :
print("Not Possible");
# This code is converted by Yash_R
C#
using System;
class GFG
{
static int [,]dp = new int[1000,1000];
// Checking for prime
static bool isprime(long num){
int i;
if (num <= 1)
return false;
for (i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Conversion of string to int
static long convert(String s, int i, int j)
{
long temp = 0;
int k;
for (k = i; k <= j; k++) {
temp = temp * 10 + (s[k] - '0');
}
return temp;
}
// Function to get the minimum splits
static int solve(String s, int i, int j)
{
int k;
// Convert the segment to integer or long long
long num = convert(s, i, j);
// Number is prime
if (isprime(num)) {
return 0;
}
// If a single digit is prime
if (i == j && isprime(num))
return 0;
// If single digit is not prime
if (i == j && isprime(num) == false)
return int.MaxValue;
if (dp[i,j] != 0)
return dp[i, j];
int ans = int.MaxValue;
for (k = i; k < j; k++) {
// Recur for left segment
int left = solve(s, i, k);
if (left == int.MaxValue) {
continue;
}
// Recur for right segment
int right = solve(s, k + 1, j);
if (right == int.MaxValue) {
continue;
}
// Minimum from left and right segment
ans = Math.Min(ans, 1 + left + right);
}
return dp[i,j] = ans;
}
public static void Main(String []args)
{
String s = "2352";
int n = s.Length;
int cuts = solve(s, 0, n - 1);
if (cuts != int.MaxValue) {
Console.Write(cuts);
}
else {
Console.Write("Not Possible");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
let dp = new Array(1000);
for(let i = 0; i < 1000; i++){
dp[i] = new Array(1000)
}
// Checking for prime
function isprime(num)
{
if (num <= 1)
return false;
for (let i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Conversion of string to int
function convert(s, i, j)
{
let temp = 0;
for (let k = i; k <= j; k++) {
temp = temp * 10 + (s[k] - '0');
}
return temp;
}
// Function to get the minimum splits
function solve(s, i, j)
{
// Convert the segment to integer or long long
let num = convert(s, i, j);
// Number is prime
if (isprime(num)) {
return 0;
}
// If a single digit is prime
if (i == j && isprime(num))
return 0;
// If single digit is not prime
if (i == j && isprime(num) == false)
return Number.MAX_SAFE_INTEGER;
if (dp[i][j])
return dp[i][j];
let ans = Number.MAX_SAFE_INTEGER;
for (let k = i; k < j; k++) {
// Recur for left segment
let left = solve(s, i, k);
if (left == Number.MAX_SAFE_INTEGER) {
continue;
}
// Recur for right segment
let right = solve(s, k + 1, j);
if (right == Number.MAX_SAFE_INTEGER) {
continue;
}
// Minimum from left and right segment
ans = Math.min(ans, 1 + left + right);
}
return dp[i][j] = ans;
}
let s = "2352";
let n = s.length;
let cuts = solve(s, 0, n - 1);
if (cuts != Number.MAX_SAFE_INTEGER) {
document.write(cuts);
}
else {
document.write("Not Possible");
}
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
2
Complejidad del tiempo: O(n 3/2 )
Espacio Auxiliar: O(10 6 )
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA