Minimum number of Factorials whose sum is equal to N
Given a number N (<1010), the task is to find the minimum number of factorials needed to represent N, as their sum. Also, print those factorials.
Examples:
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
Approach:
- In order to efficiently find the factorials which are needed to represent N as their sum, we can precompute the factorials till N (N < 1010) and store them in an array, for faster calculations.
- Then using Greedy Algorithm, we can take largest factorials from this array which can be added to represent N.
- Start from largest possible factorial and keep adding factorials while the remaining value is greater than 0.
- Below is the complete algorithm.
- Initialize result as empty
- find the largest factorial that is smaller than N
- Add found factorial to result. Subtract value of found factorial from N
- If N becomes 0, then print result. Else repeat steps 2 and 3 for new value of N
Below is the implementation of the above approach:
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> |
Output:
3 24 2 1
Time Complexity: O(N * size)
Auxiliary Space: O(N * size)
Contact Us