-5
\$\begingroup\$

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

  }
\$\endgroup\$
5
  • 3
    \$\begingroup\$ First up indentation. Second with these kind of challenges it's usually about finding a trick to do less work. \$\endgroup\$ Mar 10, 2016 at 15:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Mar 10, 2016 at 16:29
  • 2
    \$\begingroup\$ "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 \$\endgroup\$ Mar 10, 2016 at 16:54
  • \$\begingroup\$ can you please modify the above code?? \$\endgroup\$
    – Pub Insta
    Mar 10, 2016 at 16:56
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ Mar 10, 2016 at 17:00

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
    

}

\$\endgroup\$
2
  • \$\begingroup\$ Could you elaborate on how and why your changes improve the OPs code? Code dumps generally aren't well-received here on Code Review. \$\endgroup\$ Mar 10, 2016 at 18:38
  • \$\begingroup\$ Ah, got you (sorry, misread things before). Added some elaboration \$\endgroup\$ Mar 10, 2016 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.