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.
Producción
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