title: Debugging a Sums of Digit Factorials
body: <p>I would to solve this problem illustrated in this image using C++</p>
  <blockquote>
  <p>Define f(n) as the sum of the factorials of the digits of n. For example, f(342) = 3! + 4! + 2! = 32.</p>
  <p>Define sf(n) as the sum of the digits of f(n). So sf(342) = 3 + 2 = 5.</p>
  <p>Define g(i) to be the smallest positive integer n such that sf(n) = i. Though sf(342) is 5, sf(25) is also 5, and it can be verified that g(5) is 25.</p>
  <p>Define sg(i) as the sum of the digits of g(i). So sg(5) = 2 + 5 = 7.</p>
  <p>Further, it can be verified that g(20) is 267 and ∑ sg(i) for 1 ≤ i ≤ 20 is 156.</p>
  <p>What is ∑ sg(i) for 1 ≤ i ≤ 150?</p>
  </blockquote>
  <p>Image:</p>
  <p><img src="https://i.stack.imgur.com/sTIYY.jpg" alt="enter image description here" /></p>
  <p>Here is my approach. My code takes long time running, and it works</p>
  <pre><code>#include &lt;cmath&gt;
  #include &lt;cstdio&gt;
  #include &lt;vector&gt;
  #include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  int factorial(int n);
  std::vector&lt;int&gt; int_to_vector(int n);
  int sum_vector(std::vector&lt;int&gt; v);
  int get_smallest_number(std::vector&lt;int&gt; v, int sum, int n);
  int sum_sg(int n )
  
  
  int main() {
      /* Enter your code here. Read input from STDIN. Print output to STDOUT */
      int q;
      int m,n;
      int g;
      int sum = 0;
      std::vector&lt;int&gt; vec;
      
      cin&gt;&gt;q;
      if( 1&lt;=q &amp;&amp; q&lt;=100000){
          
      std::vector&lt;int&gt; s;
      int fact = 0;
      int sg = 0;
      for ( int i = 0; i &lt; q; i++){
          
         cin&gt;&gt;n&gt;&gt;m;
         fact = factorial(n);
         s = int_to_vector(fact);
         sum = sum_vector(s);
         g = get_smallest_number(s, sum, n);
         s = int_to_vector(g);
         sum = sum_vector(s);
      
      }
      
      }
      
         
      return 0;
  }
  
  int factorial(int n){
   
   if (n==0) return 1;
   return factorial(n-1)*n;     
  }
  
  std::vector&lt;int&gt; int_to_vector(int n){
      
      std::vector&lt;int&gt; numbers;
       while(n&gt;0)
      {
           numbers.push_back(n%10);
           n/=10;
      }
      return numbers;
  }
  
  int sum_vector(std::vector&lt;int&gt; v){
      
      int sum=0;
      
      for(int i = 0; i &lt; v.size(); i++){
          
          sum+=v.at(i);
      }
      
      return sum;  
  }
  
  int get_smallest_number(std::vector&lt;int&gt; v, int sum, int n){
      
      int i = 0;
      int factoriel = 1;
      std::vector&lt;int&gt; vect;
      int sum2 = 0;
      
      
  while( i &lt; n){
      
      factoriel = factorial(i);
      vect = int_to_vector(factoriel);
      sum2 = sum_vector(vect);
      
      if( sum2 == sum) return i;
      
      i++ ;
  }
  
  return n;
      
  }
  
  </code></pre>
  <p>I think on recursive solutions, but it seems somehow more complex to implement. Are there any solutions using modern C++ and STL?</p>