Dado un entero N y la string entera M , la tarea es encontrar el recuento total para hacer N usando los dígitos de la string M. Además, el dígito 2 se puede tratar como el dígito 5 , y el dígito 6 se puede tratar como el dígito 9 y viceversa, y cada dígito de la string M se puede usar como máximo una vez.
Ejemplos:
Entrada: N = 6, M = “245769”
Salida: 2
Explicación: Los dígitos 5 y 6 se usan para formar el número 56. iop[Los dígitos 2 y 9 se usan para formar el número 56. Como 2 se trata como 5 y 9 se trata como 6.Entrada: N = 25, M = “55”
Salida: 1
Enfoque: El problema dado se puede resolver mediante Hashing . Siga los pasos a continuación para resolver el problema:
- Cree un hashmap vacío , digamos un mapa para almacenar la frecuencia de los dígitos de la string M dada .
- Cree una variable, digamos, len para almacenar la longitud de la string .
- Recorra la string S dada usando la variable i e itere hasta que el valor de i sea menor que len y realice los siguientes pasos:
- Si el carácter S[i] es igual a ‘5’ , cámbielo a ‘2’ .
- Si el carácter S[i] es igual a ‘9’ , cámbielo a ‘6’.
- Si el carácter está presente en mymap , cambie la frecuencia como mymap.put(x, map.get(x)+1).
- De lo contrario, inserte el carácter en el mapa con la frecuencia 1 como mymap.put(x, 1) .
- Después de agregar la frecuencia al mapa, incremente i y continúe con la siguiente iteración.
- Cree un hashmap vacío , diga rems para almacenar los dígitos del número N.
- Iterar hasta que el valor de N sea mayor que 0 y realizar los siguientes pasos:
- Cree una variable, digamos rem para almacenar el último dígito de N usando el operador de módulo como N%10 .
- Si rem es igual a 5 , cámbielo a 2 .
- Si rem es igual a 9 , cámbialo a 6 .
- Si el rem está presente en el mapa de rems , aumente la frecuencia en 1 como rems.put(rem, rems.get(rem)+1) .
- De lo contrario, insértelo en el mapa de rems como rems.put(rem, 1) .
- Divide N por 10.
- Cree una variable, digamos cnt , para almacenar el conteo máximo del número N que se puede formar usando los dígitos dados de la string M .
- Atraviese el mapa rems y realice los siguientes pasos:
- Deje que cada objeto en el mapa sea ele.
- Compruebe si la clave de ele está presente en el mapa de frecuencia de la string mymap .
- Si no está presente, el retorno 0 (El número N no se puede formar si un dígito de N no está presente en la string M).
- Calcule el conteo dividiendo la frecuencia de la clave en mymap con la frecuencia en el mapa rems como mymap.get(key)/ele.getValue() .
- Actualice el valor mínimo de todas las iteraciones en cnt .
- Después de completar los pasos anteriores, imprima el valor de cnt como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int solve(int n, string str)
{
// Store the frequency of digits
// from the given string M
map<int,int>mymap;
// Store length of the string M
int len = str.size();
// Loop to traverse the string
for (int i = 0; i < len; i++) {
char c = str[i];
// Replace 5 with 2
if (c == '5')
c = '2';
// Replace 9 with 6
else if (c == '9')
c = '6';
// Get the int form of
// the current character
// in the string
int c_int = c-'a';
// Insert in the map
if (mymap.find(c_int)!=mymap.end())
mymap[c_int] += 1;
else
mymap[c_int] =1;
}
// Store all the digits of the
// required number N
map<int,int>rems;
// Loop to get all the digits
// from the number N
while (n > 0) {
// Get the last digit as
// the remainder
int rem = n % 10;
// Replace 5 with 2
if (rem == 5)
rem = 2;
// Replace 9 with 6
if (rem == 9)
rem = 6;
// Insert the remainders
// in the rems map
if (rems.find(rem) != rems.end())
rems[rem] += 1 ;
else
rems[rem] = 1;
n = n / 10;
}
// Store the resultant count
int cnt = 1e8;
// Iterate through the rems map
for (auto ele : rems) {
// Get the key which is
// a digit from the number
// N to be formed
int key = ele.first;
// If not present in the
// string M, number N that
// cannot be formed
if (mymap.find(key)==mymap.end())
return 0;
// Divide the frequency of
// the digit from the string
// M with the frequency of
// the current remainder
int temp = mymap[key]/ele.second;
// Choose the minimum
cnt = min(cnt, temp);
}
// Return the maximum count
return cnt;
}
// Driver Code
int main()
{
int N = 56;
string M = "245769";
cout<<solve(N, M)<<endl;
return 0;
}
// This code is contributed by dwivediyash
Java
// Java program for the above approach
import java.util.HashMap;
import java.util.Map;
public class GFG {
// Function to find the count of
// numbers that can be formed using
// the given digits in the string
int solve(int n, String str)
{
// Store the frequency of digits
// from the given string M
HashMap<Integer, Integer> mymap
= new HashMap<>();
// Store length of the string M
int len = str.length();
// Loop to traverse the string
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
// Replace 5 with 2
if (c == '5')
c = '2';
// Replace 9 with 6
else if (c == '9')
c = '6';
// Get the int form of
// the current character
// in the string
int c_int = Integer.parseInt(
String.valueOf(c));
// Insert in the map
if (mymap.containsKey(c_int))
mymap.put(
c_int, mymap.get(c_int) + 1);
else
mymap.put(c_int, 1);
}
// Store all the digits of the
// required number N
HashMap<Integer, Integer> rems
= new HashMap<>();
// Loop to get all the digits
// from the number N
while (n > 0) {
// Get the last digit as
// the remainder
int rem = n % 10;
// Replace 5 with 2
if (rem == 5)
rem = 2;
// Replace 9 with 6
if (rem == 9)
rem = 6;
// Insert the remainders
// in the rems map
if (rems.containsKey(rem))
rems.put(rem, rems.get(rem) + 1);
else
rems.put(rem, 1);
n = n / 10;
}
// Store the resultant count
int cnt = Integer.MAX_VALUE;
// Iterate through the rems map
for (Map.Entry<Integer, Integer> ele : rems.entrySet()) {
// Get the key which is
// a digit from the number
// N to be formed
int key = ele.getKey();
// If not present in the
// string M, number N that
// cannot be formed
if (!mymap.containsKey(key))
return 0;
// Divide the frequency of
// the digit from the string
// M with the frequency of
// the current remainder
int temp = mymap.get(key)
/ ele.getValue();
// Choose the minimum
cnt = Math.min(cnt, temp);
}
// Return the maximum count
return cnt;
}
// Driver Code
public static void main(String args[])
{
GFG obj = new GFG();
int N = 56;
String M = "245769";
System.out.println(obj.solve(N, M));
}
}
Javascript
<script>
// Javascript program for the above approach
// Function to find the count of
// numbers that can be formed using
// the given digits in the string
function solve(n, str) {
// Store the frequency of digits
// from the given string M
let mymap = new Map();
// Store length of the string M
let len = str.length;
// Loop to traverse the string
for (let i = 0; i < len; i++) {
let c = str.charAt(i);
// Replace 5 with 2
if (c == "5") c = "2";
// Replace 9 with 6
else if (c == "9") c = "6";
// Get the int form of
// the current character
// in the string
let c_int = parseInt(c);
// Insert in the map
if (mymap.has(c_int)) mymap.set(c_int, mymap.get(c_int) + 1);
else mymap.set(c_int, 1);
}
// Store all the digits of the
// required number N
let rems = new Map();
// Loop to get all the digits
// from the number N
while (n > 0) {
// Get the last digit as
// the remainder
let rem = n % 10;
// Replace 5 with 2
if (rem == 5) rem = 2;
// Replace 9 with 6
if (rem == 9) rem = 6;
// Insert the remainders
// in the rems map
if (rems.has(rem)) rems.set(rem, rems.get(rem) + 1);
else rems.set(rem, 1);
n = Math.floor(n / 10);
}
// Store the resultant count
let cnt = Number.MAX_SAFE_INTEGER;
// Iterate through the rems map
for (let ele of rems) {
// Get the key which is
// a digit from the number
// N to be formed
let key = ele[0];
// If not present in the
// string M, number N that
// cannot be formed
if (!mymap.has(key)) return 0;
// Divide the frequency of
// the digit from the string
// M with the frequency of
// the current remainder
let temp = mymap.get(key) / ele[1];
// Choose the minimum
cnt = Math.min(cnt, temp);
}
// Return the maximum count
return cnt;
}
// Driver Code
let N = 56;
let M = "245769";
document.write(solve(N, M));
// This code is contributed by gfgking.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por avllikhita y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA