Minimum number of Factorials whose sum is equal to N | C ++ 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 ; Store the actual size of fact [ ] ; Function to precompute factorials till N ; Precomputing factorials ; Function to find the minimum number of factorials whose sum represents N ; Precompute factorials ; Initialize result ; Traverse through all factorials ; Find factorials ; Print min count ; Print result ; Driver program
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE using namespace std ; ll fact [ 14 ] ; int size = 1 ; void preCompute ( int N ) { fact [ 0 ] = 1 ; for ( int i = 1 ; fact [ i - 1 ] <= N ; i ++ ) { fact [ i ] = ( fact [ i - 1 ] * i ) ; size ++ ; } } void findMin ( int N ) { preCompute ( N ) ; int originalN = N ; vector < int > ans ; for ( int i = size - 1 ; i >= 0 ; i -- ) { while ( N >= fact [ i ] ) { N -= fact [ i ] ; ans . push_back ( fact [ i ] ) ; } } cout << ans . size ( ) << " STRNEWLINE " ; for ( int i = 0 ; i < ans . size ( ) ; i ++ ) cout << ans [ i ] << " ▁ " ; } int main ( ) { int n = 27 ; findMin ( n ) ; return 0 ; }