Prerrequisitos: Digit-DP
Dada la string str que representa un número grande, la tarea es encontrar la cantidad mínima de segmentos que la string dada se puede dividir de modo que cada segmento sea un número impar en el rango de 1 a 10 9 .
Ejemplos:
Entrada: str = “123456789123456789123”
Salida: 3
Explicación:
El número se puede dividir como {123456789, 123456789, 123}
Entrada: str = “123456”
Salida: -1
Explicación:
No podemos dividir el número dado de modo que todos los segmentos son raros
Enfoque: La idea es usar programación dinámica con la ayuda del concepto digit-dp para resolver este problema. Por lo tanto, se define una array splitDP[] donde splitDP[i] indica el número mínimo de divisiones requeridas en la string de prefijos de longitud ‘i’ para dividirla en la subdivisión impar.
La array splitDP[] se llena de la siguiente manera:
- Se utiliza un bucle para iterar a través de todos los índices de la string dada.
- Para cada índice ‘i’ del ciclo anterior, se itera otro ciclo del 1 al 9 para verificar si la substring del índice (i + j) es impar o no.
- Si forma un número impar, entonces el valor en splitDP[] se actualiza como:
splitDP[i + j] = min(splitDP[i + j], 1 + splitDP[i]);
- Después de actualizar todos los valores de la array, el valor en el último índice es el número mínimo de divisiones para toda la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to split the given string into odds #include <bits/stdc++.h> using namespace std; // Function to check whether a string // is an odd number or not bool checkOdd(string number) { int n = number.length(); int num = number[n - 1] - '0'; return (num & 1); } // A function to find the minimum // number of segments the given string // can be divided such that every // segment is a odd number int splitIntoOdds(string number) { int numLen = number.length(); // Declare a splitdp[] array // and initialize to -1 int splitDP[numLen + 1]; memset(splitDP, -1, sizeof(splitDP)); // Build the DP table in // a bottom-up manner for (int i = 1; i <= numLen; i++) { // Initially Check if the entire prefix is odd if (i <= 9 && checkOdd(number.substr(0, i))) splitDP[i] = 1; // If the Given Prefix can be split into Odds // then for the remaining string from i to j // Check if Odd. If yes calculate // the minimum split till j if (splitDP[i] != -1) { for (int j = 1; j <= 9 && i + j <= numLen; j++) { // To check if the substring from i to j // is a odd number or not if (checkOdd(number.substr(i, j))) { // If it is an odd number, // then update the dp array if (splitDP[i + j] == -1) splitDP[i + j] = 1 + splitDP[i]; else splitDP[i + j] = min(splitDP[i + j], 1 + splitDP[i]); } } } } // Return the minimum number of splits // for the entire string return splitDP[numLen]; } // Driver code int main() { cout << splitIntoOdds("123456789123456789123") << "\n"; return 0; }
Java
// Java program to split the given string into odds class GFG { // Function to check whether a string // is an odd number or not static int checkOdd(String number) { int n = number.length(); int num = number.charAt(n - 1) - '0'; return (num & 1); } // A function to find the minimum // number of segments the given string // can be divided such that every // segment is a odd number static int splitIntoOdds(String number) { int numLen = number.length(); // Declare a splitdp[] array // and initialize to -1 int splitDP[] = new int[numLen + 1]; for(int i= 0; i < numLen + 1; i++) splitDP[i] = -1; // Build the DP table in // a bottom-up manner for (int i = 1; i <= numLen; i++) { // Initially Check if the entire prefix is odd if (i <= 9 && (checkOdd(number.substring(0, i)) == 1)) splitDP[i] = 1; // If the Given Prefix can be split into Odds // then for the remaining string from i to j // Check if Odd. If yes calculate // the minimum split till j if (splitDP[i] != -1) { for (int j = 1; j <= 9 && i + j <= numLen; j++) { // To check if the substring from i to j // is a odd number or not if (checkOdd(number.substring(i, i + j)) == 1) { // If it is an odd number, // then update the dp array if (splitDP[i + j] == -1) splitDP[i + j] = 1 + splitDP[i]; else splitDP[i + j] = Math.min(splitDP[i + j], 1 + splitDP[i]); } } } } // Return the minimum number of splits // for the entire string return splitDP[numLen]; } // Driver code public static void main (String[] args) { System.out.println(splitIntoOdds("123456789123456789123")); } } // This code is contributed by AnkitRai01
Python3
# Python3 program to split the given string into odds # Function to check whether a string # is an odd number or not def checkOdd(number): n = len(number) num = ord(number[n - 1]) - 48 return (num & 1) # A function to find the minimum # number of segments the given string # can be divided such that every # segment is a odd number def splitIntoOdds(number): numLen = len(number) # Declare a splitdp[] array # and initialize to -1 splitDP = [-1 for i in range(numLen + 1)] # Build the DP table in # a bottom-up manner for i in range(1, numLen + 1): # Initially Check if the entire prefix is odd if (i <= 9 and checkOdd(number[0:i]) > 0): splitDP[i] = 1 # If the Given Prefix can be split into Odds # then for the remaining string from i to j # Check if Odd. If yes calculate # the minimum split till j if (splitDP[i] != -1): for j in range(1, 10): if(i + j > numLen): break; # To check if the substring from i to j # is a odd number or not if (checkOdd(number[i:i + j])): # If it is an odd number, # then update the dp array if (splitDP[i + j] == -1): splitDP[i + j] = 1 + splitDP[i] else: splitDP[i + j] = min(splitDP[i + j], 1 + splitDP[i]) # Return the minimum number of splits # for the entire string return splitDP[numLen] # Driver code print(splitIntoOdds("123456789123456789123")) # This code is contributed by Sanjit_Prasad
C#
// C# program to split the given string into odds using System; class GFG { // Function to check whether a string // is an odd number or not static int checkOdd(string number) { int n = number.Length; int num = number[n - 1] - '0'; return (num & 1); } // A function to find the minimum // number of segments the given string // can be divided such that every // segment is a odd number static int splitIntoOdds(string number) { int numLen = number.Length; // Declare a splitdp[] array // and initialize to -1 int []splitDP = new int[numLen + 1]; for(int i= 0; i < numLen + 1; i++) splitDP[i] = -1; // Build the DP table in // a bottom-up manner for (int i = 1; i <= numLen; i++) { // Initially Check if the entire prefix is odd if (i <= 9 && (checkOdd(number.Substring(0, i)) == 1)) splitDP[i] = 1; // If the Given Prefix can be split into Odds // then for the remaining string from i to j // Check if Odd. If yes calculate // the minimum split till j if (splitDP[i] != -1) { for (int j = 1; j <= 9 && i + j <= numLen; j++) { // To check if the substring from i to j // is a odd number or not if (checkOdd(number.Substring(i, j)) == 1) { // If it is an odd number, // then update the dp array if (splitDP[i + j] == -1) splitDP[i + j] = 1 + splitDP[i]; else splitDP[i + j] = Math.Min(splitDP[i + j], 1 + splitDP[i]); } } } } // Return the minimum number of splits // for the entire string return splitDP[numLen]; } // Driver code public static void Main (string[] args) { Console.WriteLine(splitIntoOdds("123456789123456789123")); } } // This code is contributed by AnkitRai01
Javascript
<script> // JavaScript program to split the // given string into odds // Function to check whether a string // is an odd number or not function checkOdd(number) { let n = number.length; let num = number[n - 1] - '0'; return (num & 1); } // A function to find the minimum // number of segments the given string // can be divided such that every // segment is a odd number function split intoOdds(number) { let numLen = number.length; // Declare a splitdp[] array // and initialize to -1 let splitDP = Array.from({length: numLen + 1}, (_, i) => 0); for(let i= 0; i < numLen + 1; i++) splitDP[i] = -1; // Build the DP table in // a bottom-up manner for (let i = 1; i <= numLen; i++) { // Initially Check if the // entire prefix is odd if (i <= 9 && (checkOdd(number.substr(0, i)) == 1)) splitDP[i] = 1; // If the Given Prefix can // be split into Odds // then for the remaining // string from i to j // Check if Odd. // If yes calculate // the minimum split till j if (splitDP[i] != -1) { for (let j = 1; j <= 9 && i + j <= numLen; j++) { // To check if the // substring from i to j // is a odd number or not if (checkOdd(number.substr(i, i + j)) == 1) { // If it is an odd number, // then update the dp array if (splitDP[i + j] == -1) splitDP[i + j] = 1 + splitDP[i]; else splitDP[i + j] = Math.min(splitDP[i + j], 1 + splitDP[i]); } } } } // Return the minimum number of splits // for the entire string return splitDP[numLen]; } // Driver code document.write(splitintoOdds("123456789123456789123")); </script>
3
Complejidad de tiempo: O(N)
Espacio auxiliar: O(numLen)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA