Número máximo con producto factorial del mismo dígito

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *