Find the sum of all numbers below N which divide the sum of the factorial of their digits

Question

\$19!\$ is a curious number, as \$1!+9!=1+362880=362881\$ is divisible by \$19\$.

Find the sum of all numbers below \$N\$ which divide the sum of the factorial of their digits. Note: as \$1!,2!,\cdots,9!\$ are not sums, so they are not included.

Input Format: Input contains an integer \$N\$

Output Format: Print the answer corresponding to the test case.

Constraints: \$10^1 \le N \le 10^5\$

Sample Input

20

Sample Output

19

In the program below I am getting time limit exceeded error.

       #include <iostream>
   using namespace std;

  int main() {
int remainder;
 int sum = 0,belowN=0;
   int c,factorial = 1,sumat=0;
 int N,i=10;
   cin>>N;
while(i<N-1)
{

c=i;

 while (i>0) {
remainder = i%10;
sum = sum + remainder;
int digit = i%10;
i = i/10;
 // cout<<digit << endl;
for(int j=1;j<=digit;j++)
factorial *= j; 
sumat=sumat+factorial;

 // cout<<factorial<<endl;
factorial=1;
}
if(sumat%c==0)
 belowN= belowN+c;
 i++;
     }
   cout<<belowN;
   return 0;

  }

Answer 1

An example how precalculating the single digit factorials could make it faster even without any particular other optimization;

#include <iostream>
#include <vector>

std::vector<int> factorials;

// Takes a number and adds the factorials of the digits recursively
int digitMult(int x) { return x == 0 ? 0 : factorials[x%10] + digitMult(x/10); }

// A basic factorial method for calculating fact(0..9) below
int fact(int x)      { return x == 0 ? 1 : x * fact(x - 1); }

int main() {
  for(int i=0; i<10; i++)               // Precalculate fact(0..9)
    factorials.push_back(fact(i));

  for(int i=10; i<100000; i++)
    if(digitMult(i) % i == 0)
      std::cout << i << std::endl;
}

$ time ./a.out  
19 56 71 93 145 219 758 768 7584 7684 9696 10081 21993 40585

real    0m0.004s  
user    0m0.002s  
sys     0m0.002s

A somewhat cleaned up version of your existing code is also probably fast enough;

#include <iostream>
using namespace std;

int main() {

  int belowN=0;
  int c, factorial,sumat=0;
  int N,i=10;

  cin>>N;

  while(i<N)
  {
    c=i;
    sumat = 0;
    while (c>0) {
      int digit = c%10;
      c = c/10;
      factorial=1;
      for(int j=1;j<=digit;j++)
        factorial *= j;
      sumat=sumat+factorial;
    }
    if(sumat%i==0)
      belowN= belowN+i;
    i++;
  }
  cout<<belowN << endl;
  return 0;
}

The main changes are to do the calculations with the existing c variable instead of i that you're looping over, and the elimination of some unused variables.

Answer 2

Working version (note: it hardwires N because the online C++ compiler I used doesn't do input). And it's basically C-in-C++, but then so was your original.

There were a number of issues with your original code: Variables weren't re-initialised c

1. And in general, I felt the code was trying to do much in one go, instead of breaking down the problem into its constituent parts.
2. Variables weren't re-initialised correctly each time around the main loop.
3. There was code/variables remaining from earlier versions that were no longer used.
4. There was confusion about which variable was controlling the loop and which were used for intermediate computations
5. Several loops fitted the form of a for-loop (initialise a variable,check at the top of the loop, make a change to the loop variable at the end of the loop) but used whiles instead.

The revised code

• puts each part (calculate factorial, calculate sum-of-factorials, do the previous for 10...N) in to separate functions, This addresses 1, 2, 3, and 4.

  1. Each function does just one thing, making it clearer (and testable in isolation without having to get the whole program working)
  2. A function re-initialises its (auto) local variables each time it's called, meaning they will get initialised
  3. a function that does just one thing makes it easier to see redundant code
  4. the variables used in a function can't interfere with those outside or vice versa (when all are passed by value, anyway, as is the case here)

• Refactors the while loops into for loops, so addressing 5. Keeping everything about the operation of the loop in one place is clearer.

  #include <iostream>
  
  using namespace std;
  
  int fact(int i) 
  {   
      int f = 1;
      for (int n = 1; n <= i; n++) f = f * n;
      return f;
  }
  
  int sumFacts(int c)
  {
      int total = 0;
      while (c>0) {
          total = total + fact(c%10) ;
          c = c/10;
      }
      return total;
  }
  
  
  int main()
  {
    int belowN=0;
    int N;
    N = 100000;
  
    for(int i = 10; i<N-1; i ++)
    {
      if (sumFacts(i)%i == 0)
          belowN = belowN + i;
    }
     cout<<belowN;
     return 0;
  

}