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

$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;

}
• First up indentation. Second with these kind of challenges it's usually about finding a trick to do less work. – ratchet freak Mar 10 '16 at 15:41
• You could e.g. precalculate the factorials for the digits and store them into an array, so you don't need to calculate them every time. – Simon Kraemer Mar 10 '16 at 16:29
• "i = i/10;" This screws up your while loop. You need to not change i in the loop. So I don't care how fast it runs, it will give you the wrong answer. And you never use sum or remainder – The Archetypal Paul Mar 10 '16 at 16:54
• can you please modify the above code?? – Pub Insta Mar 10 '16 at 16:56
• And you don't reset factorial back to 1 for each digit. Basically, this code is broken in many ways. Walk through it in a debugger, break the calculation into separate functions (e.g. one to calculate factorial, another to calculate sum-of-factorials-of-digits) and it will be easier to get correct – The Archetypal Paul Mar 10 '16 at 17:00

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.

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;
}
}

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;

}

• Could you elaborate on how and why your changes improve the OPs code? Code dumps generally aren't well-received here on Code Review. – Ethan Bierlein Mar 10 '16 at 18:38
• Ah, got you (sorry, misread things before). Added some elaboration – The Archetypal Paul Mar 10 '16 at 19:25