**[Link to the original problem][1]**

It&#39;s not a homework question. I just thought that someone might know a real solution to this problem.

I was on a programming contest back in 2004, and there was this problem:

&gt; Given n, find sum of digits of n!. n can be from 0 to 10000. Time limit: 1 second. I think there was up to 100 numbers for each test set.

My solution was pretty fast but not fast enough, so I just let it run for some time. It built an array of pre-calculated values which I could use in my code. It was a hack, but it worked.

But there was a guy, who solved this problem with about 10 lines of code and it would give an answer in no time. I believe it was some sort of dynamic programming, or something from number theory. We were 16 at that time so it should not be a &quot;rocket science&quot;. 

Does anyone know what kind of an algorithm he could use?

**EDIT**: I&#39;m sorry if I didn&#39;t made the question clear. As mquander said, there should be a clever solution, without bugnum, with just plain Pascal code, couple of loops, O(n&lt;sup&gt;2&lt;/sup&gt;) or something like that. 1 second is not a constraint anymore.

I found [here][2] that if n &gt; 5, then 9 divides sum of digits of a factorial. We also can find how many zeros are there at the end of the number. Can we use that?

Ok, another problem from programming contest from Russia. Given 1 &lt;= N &lt;= 2 000 000 000, output N! mod (N+1). Is that somehow related?


  [1]: http://acm.uva.es/p/v102/10220.html
  [2]: http://research.att.com/~njas/sequences/A004152

All Sum of-Digits Solutions on Gang of Coders

Total of 1 Sum of-Digits Solutions

Sum of digits of a factorial