Dado un número entero N y un vector de strings prefijos[], la tarea es calcular el total de strings posibles de longitud N desde los caracteres ‘0’ a ‘9’ . tal que los prefijos dados no se pueden usar en ninguna de las strings.
Ejemplos:
Entrada: N = 3, prefijos = {“42”}
Salida : 990
Explicación: Todas las strings excepto{“420”, “421”, “422”, “423”, “424”, “425”, “426”, “427”, “428”, “429”} son válidos.Entrada: N = 5, prefijos[]= { “0”, “1”, “911” }
Salida: 79900
Enfoque: el total de strings posibles con longitud es (10 ^ N) ya que para cada lugar en una string hay 10 opciones de carácter. En lugar de calcular el total de strings buenas, reste el total de strings malas del total de strings. Antes de iterar sobre los prefijos, la combinación de prefijos con el mismo carácter inicial que el prefijo de mayor longitud podría dar lugar a la sustracción de algunas repeticiones. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable total como 10 N .
- Inicialice un map<int, vector<string>> mp[].
- Itere sobre el rango [0, M) usando la variable i y realice las siguientes tareas:
- Introduzca el valor de los prefijos[i] en el vector del mapa mp[prefijos[i]-‘0’].
- Inicialice el vector new_prefixes[] .
- Recorra el mapa mp[] usando la variable x y realice las siguientes tareas:
- Inicialice la variable mn como N .
- Recorra el vector x.segundo usando la variable p y realice las siguientes tareas:
- Establezca el valor de mn como el mínimo de mn o p.length() .
- Recorra el vector x.segundo usando la variable p y realice las siguientes tareas:
- Si p.length() es menor que mn, entonces inserte p en el vector new_prefixes[] .
- Itere sobre el rango [0, new_prefixes.size()) usando la variable i y realice las siguientes tareas:
- Reste el valor int(pow(10, N – new_prefixes[i].length())+ 0.5) del total de la variable .
- Después de realizar los pasos anteriores, imprima el valor del total como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement the above approach #include <bits/stdc++.h> using namespace std; // Change int to long long in case of overflow!! // Function to calculate total strings of length // N without the given prefixes int totalGoodStrings(int N, vector<string> prefixes) { // Calculate total strings present int total = int(pow(10, N) + 0.5); // Make a map and insert the prefixes with same // character in a vector map<int, vector<string> > mp; for (int i = 0; i < prefixes.size(); i++) { mp[prefixes[i][0] - '0'] .push_back(prefixes[i]); } // Make a new vector of prefixes strings vector<string> new_prefixes; // Iterate for each starting character for (auto x : mp) { int mn = N; // Iterate through the vector to calculate // minimum size prefix for (auto p : x.second) { mn = min(mn, int(p.length())); } // Take all the minimum prefixes in the new // vector of prefixes for (string p : x.second) { if (p.length() > mn) { continue; } new_prefixes.push_back(p); } } // Iterate through the new prefixes for (int i = 0; i < new_prefixes.size(); i++) { // Subtract bad strings total -= int(pow(10, N - new_prefixes[i].length()) + 0.5); } return total; } // Driver Code int main() { int N = 5; vector<string> prefixes = { "1", "0", "911" }; cout << totalGoodStrings(N, prefixes); return 0; }
Java
// Java Program to implement the above approach import java.util.ArrayList; import java.util.HashMap; class GFG { // Change int to long long in case of overflow!! // Function to calculate total strings of length // N without the given prefixes public static int totalGoodStrings(int N, String[] prefixes) { // Calculate total strings present int total = (int) (Math.pow(10, N) + 0.5); // Make a map and insert the prefixes with same // character in a vector HashMap<Integer, ArrayList<String>> mp = new HashMap<Integer, ArrayList<String>>(); for (int i = 0; i < prefixes.length; i++) { int key = (int) prefixes[i].charAt(0) - (int) '0'; if (mp.containsKey(key)) { ArrayList<String> temp = mp.get(key); temp.add(prefixes[i]); mp.put(key, temp); } else { ArrayList<String> temp = new ArrayList<String>(); temp.add(prefixes[i]); mp.put(key, temp); } } // Make a new vector of prefixes strings ArrayList<String> new_prefixes = new ArrayList<String>(); // Iterate for each starting character for (Integer x : mp.keySet()) { int mn = N; // Iterate through the vector to calculate // minimum size prefix for (String p : mp.get(x)) { mn = Math.min(mn, p.length()); } // Take all the minimum prefixes in the new // vector of prefixes for (String p : mp.get(x)) { if (p.length() > mn) { continue; } new_prefixes.add(p); } } // Iterate through the new prefixes for (int i = 0; i < new_prefixes.size(); i++) { // Subtract bad strings total -= (int) (Math.pow(10, N - new_prefixes.get(i).length()) + 0.5); } return total; } // Driver Code public static void main(String args[]) { int N = 5; String[] prefixes = { "1", "0", "911" }; System.out.println(totalGoodStrings(N, prefixes)); } } // This code is contributed by gfgking.
Python3
# python Program to implement the above approach import math # Change int to long long in case of overflow!! # Function to calculate total strings of length # N without the given prefixes def totalGoodStrings(N, prefixes): # Calculate total strings present total = int(math.pow(10, N) + 0.5) # Make a map and insert the prefixes with same # character in a vector mp = {} for i in range(0, len(prefixes)): if (ord(prefixes[i][0]) - ord('0')) in mp: mp[ord(prefixes[i][0]) - ord('0')].append(prefixes[i]) else: mp[ord(prefixes[i][0]) - ord('0')] = [prefixes[i]] # Make a new vector of prefixes strings new_prefixes = [] # Iterate for each starting character for x in mp: mn = N # Iterate through the vector to calculate # minimum size prefix for p in mp[x]: mn = min(mn, len(p)) # Take all the minimum prefixes in the new # vector of prefixes for p in mp[x]: if (len(p) > mn): continue new_prefixes.append(p) # Iterate through the new prefixes for i in range(0, len(new_prefixes)): # Subtract bad strings total -= int(pow(10, N - len(new_prefixes[i])) + 0.5) return total # Driver Code if __name__ == "__main__": N = 5 prefixes = ["1", "0", "911"] print(totalGoodStrings(N, prefixes)) # This code is contributed by rakeshsahni
C#
// C# Program to implement the above approach using System; using System.Collections.Generic; class GFG { // Change int to long long in case of overflow!! // Function to calculate total strings of length // N without the given prefixes public static int totalGoodStrings(int N, string[] prefixes) { // Calculate total strings present int total = (int)(Math.Pow(10, N) + 0.5); // Make a map and insert the prefixes with same // character in a vector Dictionary<int, List<string> > mp = new Dictionary<int, List<string> >(); for (int i = 0; i < prefixes.Length; i++) { int key = (int)prefixes[i][0] - (int)'0'; if (mp.ContainsKey(key)) { List<string> temp = mp[key]; temp.Add(prefixes[i]); mp[key] = temp; } else { List<string> temp = new List<string>(); temp.Add(prefixes[i]); mp[key] = temp; } } // Make a new vector of prefixes strings List<string> new_prefixes = new List<string>(); // Iterate for each starting character foreach(int x in mp.Keys) { int mn = N; // Iterate through the vector to calculate // minimum size prefix foreach(string p in mp[x]) { mn = Math.Min(mn, p.Length); } // Take all the minimum prefixes in the new // vector of prefixes foreach(string p in mp[x]) { if (p.Length > mn) { continue; } new_prefixes.Add(p); } } // Iterate through the new prefixes for (int i = 0; i < new_prefixes.Count; i++) { // Subtract bad strings total -= (int)(Math.Pow( 10, N - new_prefixes[i].Length) + 0.5); } return total; } // Driver Code public static void Main(string[] args) { int N = 5; string[] prefixes = { "1", "0", "911" }; Console.WriteLine(totalGoodStrings(N, prefixes)); } } // This code is contributed by ukasp.
Javascript
// Javascript Program to implement the above approach // Change int to long long in case of overflow!! // Function to calculate total strings of length // N without the given prefixes function totalGoodStrings(N, prefixes) { // Calculate total strings present let total = Math.floor(Math.pow(10, N) + 0.5); // Make a map and insert the prefixes with same // character in a vector let mp = new Map(); for (let i = 0; i < prefixes.length; i++) { let key = prefixes[i][0] - '0'.charCodeAt(0); if (mp.has(key)) { let temp = mp.get(key); temp.push(prefixes[i]) mp.set(key, temp) } else { mp.set(key, [prefixes[i]]) } } // Make a new vector of prefixes strings let new_prefixes = []; // Iterate for each starting character for (x of mp) { let mn = N; // Iterate through the vector to calculate // minimum size prefix for (p of x[1]) { mn = Math.min(mn, p.length); } // Take all the minimum prefixes in the new // vector of prefixes for (p of x[1]) { if (p.length > mn) { continue; } new_prefixes.push(p); } } // Iterate through the new prefixes for (let i = 0; i < new_prefixes.length; i++) { // Subtract bad strings total -= Math.floor(Math.pow(10, N - new_prefixes[i].length) + 0.5); } return total; } // Driver Code let N = 5; let prefixes = ["1", "0", "911"]; document.write(totalGoodStrings(N, prefixes)) // This code is contributed by saurabh_jaiswal.
79900
Complejidad de tiempo: O(M), donde M es el tamaño de los prefijos vectoriales[]
Espacio auxiliar: O(M*K), donde K es la longitud máxima de una string
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA