Dada una string str que representa un número entero, la tarea es encontrar el número más grande sin ceros o unos al principio o al final cuyo producto del factorial de sus dígitos sea igual al producto del factorial de los dígitos de str .
Ejemplos:
Entrada: N = 4370
Salida: 73322
4! * 3! * 7! * 0! = 7! * 3! * 3! * 2! * 2! = 725760
Entrada: N = 1280
Salida: 72222
1! * 2! * 8! * 0! = 7! * 2! * 2! * 2! * 2! = 80640
Acercarse:
- Expresar el factorial de cada una de las cifras de str como producto de factorial de números primos .
- Si str contiene solo 0 o 1 como sus dígitos, entonces mostrar el número dado como resultado no es posible sin ceros o unos al principio y al final.
- Si se encuentran los dígitos 1, 2, 3, 5 o 7 , deben incluirse como dígitos en el número resultante.
- Si se encuentran los dígitos 4, 6, 8 o 9 , expréselos como producto del factorial de números primos,
- 4! se puede expresar como 3! * 2! * 2!.
- 6! se puede expresar como 5! * 3!.
- 8! se puede expresar como 7! * 2! * 2! * 2!.
- ¡Y 9! se puede expresar como 7! * 3! * 3! * 2!.
- Finalmente, forme el número ordenando los dígitos generados en orden descendente para obtener el número máximo que satisfaga la condición.
Ilustración:
Consideremos una entrada dada 4370. El factorial de cada uno de sus dígitos es el siguiente:
4! = 24 = 2! * 2! * 3!
3! = 6 = 3!
7! = 5040 = 7!
Por lo tanto, la frecuencia de los dígitos en el número máximo es:
- La frecuencia de 7 es 1 .
- La frecuencia de 3 es 2 .
- La frecuencia de 2 es 2 .
Por lo tanto, la salida es 73322.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the required number
string getNumber(string s)
{
int number_of_digits = s.length();
int freq[10] = { 0 };
// Count the frequency of each digit
for (int i = 0; i < number_of_digits; i++) {
if (s[i] == '1'
|| s[i] == '2'
|| s[i] == '3'
|| s[i] == '5'
|| s[i] == '7') {
freq[s[i] - 48] += 1;
}
// 4! can be expressed as 2! * 2! * 3!
if (s[i] == '4') {
freq[2] += 2;
freq[3]++;
}
// 6! can be expressed as 5! * 3!
if (s[i] == '6') {
freq[5]++;
freq[3]++;
}
// 8! can be expressed as 7! * 2! * 2! * 2!
if (s[i] == '8') {
freq[7]++;
freq[2] += 3;
}
// 9! can be expressed as 7! * 3! * 3! * 2!
if (s[i] == '9') {
freq[7]++;
freq[3] += 2;
freq[2]++;
}
}
// To store the required number
string t = "";
// If number has only either 1 and 0 as its digits
if (freq[1] == number_of_digits
|| freq[0] == number_of_digits
|| (freq[0] + freq[1]) == number_of_digits) {
return s;
}
else {
// Generate the greatest number possible
for (int i = 9; i >= 2; i--) {
int ctr = freq[i];
while (ctr--) {
t += (char)(i + 48);
}
}
return t;
}
}
// Driver code
int main()
{
string s = "1280";
cout << getNumber(s);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG {
// Function to return the required number
static String getNumber(String s)
{
int number_of_digits = s.length();
int freq[] = new int[10];
// Count the frequency of each digit
for (int i = 0; i < number_of_digits; i++) {
if (s.charAt(i) == '1'
|| s.charAt(i) == '2'
|| s.charAt(i) == '3'
|| s.charAt(i) == '5'
|| s.charAt(i) == '7') {
freq[s.charAt(i) - 48] += 1;
}
// 4! can be expressed as 2! * 2! * 3!
if (s.charAt(i) == '4') {
freq[2] += 2;
freq[3]++;
}
// 6! can be expressed as 5! * 3!
if (s.charAt(i) == '6') {
freq[5]++;
freq[3]++;
}
// 8! can be expressed as 7! * 2! * 2! * 2!
if (s.charAt(i) == '8') {
freq[7]++;
freq[2] += 3;
}
// 9! can be expressed as 7! * 3! * 3! * 2!
if (s.charAt(i) == '9') {
freq[7]++;
freq[3] += 2;
freq[2]++;
}
}
// To store the required number
String t = "";
// If number has only either 1 and 0 as its digits
if (freq[1] == number_of_digits
|| freq[0] == number_of_digits
|| (freq[0] + freq[1]) == number_of_digits) {
return s;
}
else {
// Generate the greatest number possible
for (int i = 9; i >= 2; i--) {
int ctr = freq[i];
while ((ctr--)>0) {
t += (char)(i + 48);
}
}
return t;
}
}
// Driver code
public static void main (String[] args) {
String s = "1280";
System.out.println(getNumber(s));
}
}
// This code is contributed by anuj_67..
Python3
# Python3 implementation of the approach # Function to return the required number def getNumber(s): number_of_digits = len(s); freq=[0]*10; # Count the frequency of each digit for i in range(number_of_digits): if (s[i] == '1' or s[i] == '2' or s[i] == '3' or s[i] == '5' or s[i] == '7'): freq[ord(s[i]) - 48] += 1; # 4! can be expressed as 2! * 2! * 3! if (s[i] == '4'): freq[2] += 2; freq[3]+=1; # 6! can be expressed as 5! * 3! if (s[i] == '6'): freq[5]+=1; freq[3]+=1; # 8! can be expressed as 7! * 2! * 2! * 2! if (s[i] == '8'): freq[7]+=1; freq[2] += 3; # 9! can be expressed as 7! * 3! * 3! * 2! if (s[i] == '9'): freq[7]+=1; freq[3] += 2; freq[2]+=1; # To store the required number t = ""; # If number has only either 1 and 0 as its digits if (freq[1] == number_of_digits or freq[0] == number_of_digits or (freq[0] + freq[1]) == number_of_digits): return s; else: # Generate the greatest number possible for i in range(9,1,-1): ctr = freq[i]; while (ctr>0): t += chr(i + 48); ctr-=1; return t; # Driver code s = "1280"; print(getNumber(s)); # This code is contributed by mits
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// required number
static String getNumber(string s)
{
int number_of_digits = s.Length;
int []freq = new int[10];
// Count the frequency of each digit
for (int i = 0;
i < number_of_digits; i++)
{
if (s[i] == '1' || s[i] == '2' ||
s[i] == '3' || s[i] == '5' ||
s[i] == '7')
{
freq[s[i] - 48] += 1;
}
// 4! can be expressed as 2! * 2! * 3!
if (s[i] == '4')
{
freq[2] += 2;
freq[3]++;
}
// 6! can be expressed as 5! * 3!
if (s[i] == '6')
{
freq[5]++;
freq[3]++;
}
// 8! can be expressed as 7! * 2! * 2! * 2!
if (s[i] == '8')
{
freq[7]++;
freq[2] += 3;
}
// 9! can be expressed as 7! * 3! * 3! * 2!
if (s[i] == '9')
{
freq[7]++;
freq[3] += 2;
freq[2]++;
}
}
// To store the required number
string t = "";
// If number has only either 1
// and 0 as its digits
if (freq[1] == number_of_digits ||
freq[0] == number_of_digits ||
(freq[0] + freq[1]) == number_of_digits)
{
return s;
}
else
{
// Generate the greatest number possible
for (int i = 9; i >= 2; i--)
{
int ctr = freq[i];
while ((ctr--)>0)
{
t += (char)(i + 48);
}
}
return t;
}
}
// Driver code
public static void Main ()
{
string s = "1280";
Console.WriteLine(getNumber(s));
}
}
// This code is contributed by anuj_67..
PHP
<?php
// PHP implementation of the approach
// Function to return the required number
function getNumber($s)
{
$number_of_digits = strlen($s);
$freq=array_fill(0,10,0);
// Count the frequency of each digit
for ($i = 0; $i < $number_of_digits; $i++) {
if ($s[$i] == '1'
|| $s[$i] == '2'
|| $s[$i] == '3'
|| $s[$i] == '5'
|| $s[$i] == '7') {
$freq[ord($s[$i]) - 48] += 1;
}
// 4! can be expressed as 2! * 2! * 3!
if ($s[$i] == '4') {
$freq[2] += 2;
$freq[3]++;
}
// 6! can be expressed as 5! * 3!
if ($s[$i] == '6') {
$freq[5]++;
$freq[3]++;
}
// 8! can be expressed as 7! * 2! * 2! * 2!
if ($s[$i] == '8') {
$freq[7]++;
$freq[2] += 3;
}
// 9! can be expressed as 7! * 3! * 3! * 2!
if ($s[$i] == '9') {
$freq[7]++;
$freq[3] += 2;
$freq[2]++;
}
}
// To store the required number
$t = "";
// If number has only either 1 and 0 as its digits
if ($freq[1] == $number_of_digits
|| $freq[0] == $number_of_digits
|| ($freq[0] + $freq[1]) == $number_of_digits) {
return $s;
}
else {
// Generate the greatest number possible
for ($i = 9; $i >= 2; $i--) {
$ctr = $freq[$i];
while ($ctr--) {
$t .= chr($i + 48);
}
}
return $t;
}
}
// Driver code
$s = "1280";
echo getNumber($s);
// this code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the
// required number
function getNumber(s)
{
let number_of_digits = s.length;
let freq = new Array(10);
freq.fill(0);
// Count the frequency of each digit
for (let i = 0; i < number_of_digits; i++)
{
if (s[i] == '1' || s[i] == '2' ||
s[i] == '3' || s[i] == '5' ||
s[i] == '7')
{
freq[s[i].charCodeAt() - 48] += 1;
}
// 4! can be expressed as 2! * 2! * 3!
if (s[i] == '4')
{
freq[2] += 2;
freq[3]++;
}
// 6! can be expressed as 5! * 3!
if (s[i] == '6')
{
freq[5]++;
freq[3]++;
}
// 8! can be expressed as 7! * 2! * 2! * 2!
if (s[i] == '8')
{
freq[7]++;
freq[2] += 3;
}
// 9! can be expressed as 7! * 3! * 3! * 2!
if (s[i] == '9')
{
freq[7]++;
freq[3] += 2;
freq[2]++;
}
}
// To store the required number
let t = "";
// If number has only either 1
// and 0 as its digits
if (freq[1] == number_of_digits ||
freq[0] == number_of_digits ||
(freq[0] + freq[1]) == number_of_digits)
{
return s;
}
else
{
// Generate the greatest number possible
for (let i = 9; i >= 2; i--)
{
let ctr = freq[i];
while ((ctr--)>0)
{
t += String.fromCharCode(i + 48);
}
}
return t;
}
}
let s = "1280";
document.write(getNumber(s));
</script>
Producción:
72222
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RICHIK BHATTACHARJEE y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA