Databases
StackOverflow2013
Postsdbo
POSum of digits of a factorial
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSum of digits of a factorial
    text
    copied!<p><strong><a href="http://acm.uva.es/p/v102/10220.html" rel="noreferrer">Link to the original problem</a></strong></p> <p>It's not a homework question. I just thought that someone might know a real solution to this problem.</p> <p>I was on a programming contest back in 2004, and there was this problem:</p> <blockquote> <p>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.</p> </blockquote> <p>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.</p> <p>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 "rocket science". </p> <p>Does anyone know what kind of an algorithm he could use?</p> <p><strong>EDIT</strong>: I'm sorry if I didn'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<sup>2</sup>) or something like that. 1 second is not a constraint anymore.</p> <p>I found <a href="http://research.att.com/~njas/sequences/A004152" rel="noreferrer">here</a> that if n > 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?</p> <p>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?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload