Lucas97's blog

How to compute the sum of the digits of n! (n <= 1e9) ?
By Lucas97, history, 8 years ago, In English

Hi guys, today a friend asked me about this problem. He said it was just a random problem that came to his mind. So, I don't know any OJ to submit it. Do you know any way to solve it efficienty? i.e. I know we can compute it using Java or Python, but I'm looknig for something better(Imagine you have 3s as time limit)

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
8 years ago, # |
  Vote: I like it +162 Vote: I do not like it

Usually when a new problems comes to your mind you shouldn't put specific constraints for it randomly and immediately, because it's not guaranteed it's solvable in those constraints.

→ Reply
»
8 years ago, # |
  Vote: I like it +34 Vote: I do not like it

It looks like even in oeis there is no solution: link

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You clearly didn't understand the problem and of course it will be TLE

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      For smaller n(say, n=1000), maybe it wont be a problem. eg: if v=24.5, we can break up the number into smaller parts(maybe) and then multiply, such as 10^9 * 10^9 * 10^(6.5) . Only the last multiplicand will contribute to the final answer. Although, I'm not exactly convinced how this can be??

      Like Kingofnumbers said, n<=10^9 is not a good solvable limit here.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My experience tells me that you can solve this type of problem by using math, which will help you reduce numbers of calculation.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this type of problem won't ask you to calculate n! (n <= 10^9) because it seems impossible to be solved in time. Calculating n! may be a part of calulating the main question.

    → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it -28 Vote: I do not like it

Hello, a member of my team used the stirling formula to find number of digits of factorail in the problem UVA 1185 and he got accepted

xd fofao_funk comment in blog http://mirror.codeforces.com/blog/entry/44112?#comment-287711. how to solve your problem and I understand omega(n) time complexity algorithm to sum number of digits of n!.

link to problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3626

reference: https://es.wikipedia.org/wiki/F%C3%B3rmula_de_Stirling

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    This is not what op asked..

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Thanks, I forgot the other blog, I just modified the comment.

      → Reply