Número mínimo de Factoriales cuya suma es igual a N

Posted on by Rudeus Greyrat

Dado un número N (<10 10 ), la tarea es encontrar el número mínimo de factoriales necesarios para representar N, como su suma. Además, imprima esos factoriales.
Ejemplos: 
 

Input: N = 30
Output: 2
24, 6
Explanation:
Factorials needed to represent 30: 24, 6

Input: N = 150
Output: 3
120, 24, 6
Explanation:
Factorials needed to represent 150: 120 24 6

Enfoque : 
 

  1. Para encontrar eficientemente los factoriales que se necesitan para representar a N como su suma, podemos precalcular los factoriales hasta N (N < 10 10 ) y almacenarlos en una array, para cálculos más rápidos.
     
  2. Luego, usando el algoritmo codicioso , podemos tomar los factoriales más grandes de esta array que se pueden agregar para representar N. 
     
  3. Comience desde el factorial más grande posible y siga agregando factoriales mientras el valor restante sea mayor que 0. 
     
  4. A continuación se muestra el algoritmo completo.
    • Inicializar resultado como vacío
    • encontrar el factorial más grande que es más pequeño que N
    • Agregue el factorial encontrado al resultado. Reste el valor del factorial encontrado de N
    • Si N se convierte en 0, imprima el resultado. De lo contrario, repita los pasos 2 y 3 para el nuevo valor de N

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find minimum number of factorials
 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Array to calculate all factorials
// less than or equal to N
// Since there can be only 14 factorials
// till 10^10
// Hence the maximum size of fact[] is 14
ll fact[14];
 
// Store the actual size of fact[]
int size = 1;
 
// Function to precompute factorials till N
void preCompute(int N)
{
    // Precomputing factorials
    fact[0] = 1;
 
    for (int i = 1; fact[i - 1] <= N; i++) {
        fact[i] = (fact[i - 1] * i);
        size++;
    }
}
 
// Function to find the minimum number
// of factorials whose sum represents N
void findMin(int N)
{
 
    // Precompute factorials
    preCompute(N);
 
    int originalN = N;
 
    // Initialize result
    vector<int> ans;
 
    // Traverse through all factorials
    for (int i = size - 1; i >= 0; i--) {
 
        // Find factorials
        while (N >= fact[i]) {
            N -= fact[i];
            ans.push_back(fact[i]);
        }
    }
 
    // Print min count
    cout << ans.size() << "\n";
 
    // Print result
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
}
 
// Driver program
int main()
{
    int n = 27;
    findMin(n);
    return 0;
}

Java

// Java program to find minimum number of factorials
import java.util.*;
 
class GFG{
  
// Array to calculate all factorials
// less than or equal to N
// Since there can be only 14 factorials
// till 10^10
// Hence the maximum size of fact[] is 14
static int []fact = new int[14];
  
// Store the actual size of fact[]
static int size = 1;
  
// Function to precompute factorials till N
static void preCompute(int N)
{
    // Precomputing factorials
    fact[0] = 1;
  
    for (int i = 1; fact[i - 1] <= N; i++) {
        fact[i] = (fact[i - 1] * i);
        size++;
    }
}
  
// Function to find the minimum number
// of factorials whose sum represents N
static void findMin(int N)
{
  
    // Precompute factorials
    preCompute(N);
  
    int originalN = N;
  
    // Initialize result
    Vector<Integer> ans = new Vector<Integer>();
  
    // Traverse through all factorials
    for (int i = size - 1; i >= 0; i--) {
  
        // Find factorials
        while (N >= fact[i]) {
            N -= fact[i];
            ans.add(fact[i]);
        }
    }
  
    // Print min count
    System.out.print(ans.size()+ "\n");
  
    // Print result
    for (int i = 0; i < ans.size(); i++)
        System.out.print(ans.get(i)+ " ");
}
  
// Driver program
public static void main(String[] args)
{
    int n = 27;
    findMin(n);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find minimum number of factorials
 
# Array to calculate all factorials
# less than or equal to N
# Since there can be only 14 factorials
# till 10^10
# Hence the maximum size of fact[] is 14
fact = [0]*14
 
# Store the actual size of fact[]
size = 1
 
# Function to precompute factorials till N
def preCompute(N):
    global size
     
    # Precomputing factorials
    fact[0] = 1
 
    i = 1
 
    while fact[i - 1] <= N:
        fact[i] = fact[i - 1] * i
        size += 1
        i += 1
 
# Function to find the minimum number
# of factorials whose sum represents N
def findMin(N):
 
    # Precompute factorials
     
    preCompute(N)
 
    originalN = N
 
    # Initialize result
    ans = []
 
    # Traverse through all factorials
    for i in range(size-1, -1, -1):
 
        # Find factorials
        while (N >= fact[i]):
            N -= fact[i]
            ans.append(fact[i])
 
    # Print min count
    print(len(ans))
 
    # Print result
    for i in ans:
        print(i, end=" ")
 
# Driver program
 
n = 27
findMin(n)
 
# This code is contributed by mohit kumar 29

C#

// C# program to find minimum number of factorials
using System;
using System.Collections.Generic;
 
class GFG{
   
// Array to calculate all factorials
// less than or equal to N
// Since there can be only 14 factorials
// till 10^10
// Hence the maximum size of fact[] is 14
static int []fact = new int[14];
   
// Store the actual size of fact[]
static int size = 1;
   
// Function to precompute factorials till N
static void preCompute(int N)
{
    // Precomputing factorials
    fact[0] = 1;
   
    for (int i = 1; fact[i - 1] <= N; i++) {
        fact[i] = (fact[i - 1] * i);
        size++;
    }
}
   
// Function to find the minimum number
// of factorials whose sum represents N
static void findMin(int N)
{
   
    // Precompute factorials
    preCompute(N);
   
    int originalN = N;
   
    // Initialize result
    List<int> ans = new List<int>();
   
    // Traverse through all factorials
    for (int i = size - 1; i >= 0; i--) {
   
        // Find factorials
        while (N >= fact[i]) {
            N -= fact[i];
            ans.Add(fact[i]);
        }
    }
   
    // Print min count
    Console.Write(ans.Count+ "\n");
   
    // Print result
    for (int i = 0; i < ans.Count; i++)
        Console.Write(ans[i]+ " ");
}
   
// Driver program
public static void Main(String[] args)
{
    int n = 27;
    findMin(n);
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript program to find minimum number of factorials
 
// Array to calculate all factorials
// less than or equal to N
// Since there can be only 14 factorials
// till 10^10
// Hence the maximum size of fact[] is 14
var fact = Array(14).fill(0);
 
// Store the actual size of fact[]
var size = 1;
 
// Function to precompute factorials till N
function preCompute(N)
{
    // Precomputing factorials
    fact[0] = 1;
 
    for (var i = 1; fact[i - 1] <= N; i++) {
        fact[i] = (fact[i - 1] * i);
        size++;
    }
}
 
// Function to find the minimum number
// of factorials whose sum represents N
function findMin(N)
{
 
    // Precompute factorials
    preCompute(N);
 
    var originalN = N;
 
    // Initialize result
    ans = [];
 
    // Traverse through all factorials
    for (var i = size - 1; i >= 0; i--) {
 
        // Find factorials
        while (N >= fact[i]) {
            N -= fact[i];
            ans.push(fact[i]);
        }
    }
 
    // Print min count
    document.write(ans.length + "<br>");
 
    // Print result
    for (var i = 0; i < ans.length; i++)
        document.write(ans[i] + " ");
}
 
// Driver program
var n = 27;
findMin(n);
 
// This code is contributed by rutvik_56.
</script>
Producción: 

3
24 2 1

 

Complejidad de tiempo: O (N * tamaño)

Espacio auxiliar: O (N * tamaño)

Publicación traducida automáticamente

Artículo escrito por spp____ 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 *