Sum of digits of factorial problem

Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя Shuaib

Sum of digits of factorial problem

Автор Shuaib, история, 8 лет назад, По-английски

Hi,

How can I find the sum of digits in a factorial of a number N, where N can be in range [1, 2000]? Can it be done without resorting to BigNum libraries?

factorial, math

-2

Shuaib
8 лет назад
9

Комментарии (8)

Показать архивные | Написать комментарий?

AlexandruValeanu

8 лет назад, # |

Think of logarithms.

→ Ответить

Shuaib

8 лет назад, # ^ |

Can you please elaborate. I am looking for a Log(N) complexity. The algorithm given below by sbakic uses string multiplication, which won't be Log(N).

→ Ответить

AlexandruValeanu

8 лет назад, # ^ |

← Rev. 5 →

-deleted-

→ Ответить

fofao_funk

8 лет назад, # ^ |

← Rev. 4 →

Why did you delete your answer? I think it can actually work: if we know the number D of digits of the factorial F = N! and its log L = log(F), we can do some binary search in the factorial digits since log(x) is unique. For example, to find the most significant digit of the factorial we will try every 0 ≤ i ≤ 9; when $\text{[math]}$ we know that the most significant digit is i - 1. After that, we store the "current log" and do it again for the second most significant digit and for the third and so on... Overall complexity would be $\text{[math]}$ .

→ Ответить

adamant

8 лет назад, # ^ |

+13

→ Ответить

sbakic

8 лет назад, # |

-7

This is the algorithm for factorial of a number. Next step is trivial.

#include <iostream>
 
using namespace std;
 
string multy(string a, string b) {
  int n = a.size(), m = b.size();
  int array[n + m];
  for (int i = 0; i < n + m; i++) {
    array[i] = 0;
  }
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      array[i + j + 1] += (a[i] - '0') * (b[j] - '0');
    }
  }
  for (int i = n + m - 1; i >= 0; i--) {
    array[i - 1] += array[i] / 10;
    array[i] %= 10;
  }
  string s = "";
  for (int i = 0; i < n + m; i++) {
    s += array[i] + '0';
  }
  s.erase(0, min(s.find_first_not_of('0'), s.size() - 1));
  return s;
}
 
string power(int n) {
  string s = "1";
  int t = n;
  for (int i = 0; i < n; i++) {
    s = multy(s, to_string(t--));
  }
  return s;
}
 
int main(){
  int n;
  cin >> n;
  cout << power(n) << '\n';
  return 0;
}

→ Ответить