LOJ 1045 - Digits of Factorial
Tags : Logarithms, Base Conversion, Factorials, Memoization
We will be given the value of N, and the basis of the number system, base. We need to find out the number of digit(s) of the factorial of an integer (N!) in that base.
Helpful Resources
Solution
To solve this problem we can take help from logarithm formula and rules.
The value of N is given in base - 10 number system.
Let's observe what we get when we put base - 10 numbers in log10(X) :
Number |
log10(Number) |
⌊log10(Number)⌋ |
Digits |
{1, ..., 9} |
0.{something} |
0 |
1 |
{10, ..., 99} |
1.{something} |
1 |
2 |
{100, ..., 999} |
2.{something} |
2 |
3 |
... |
... |
... |
... |
X |
(Digits(X) - 1).{something} |
Digits(X) - 1 |
⌊log10(X)⌋ + 1 |
But we need to determine the number of digits for N!. So, ⌊log10(N!)⌋ + 1 will help us for base - 10.
For ⌊log10(N!)⌋, if we recall the formula for log10(X1 * X2 * X3 * ... * Xn),
log10(X1 * X2 * X3 * ... * Xn) = log10(X1) + log10(X2) + log10(X3) + ... + log10(Xn)
From the problem, we need to find out the number of digits for B-based numbers instead of 10-based. Now if we recall the base-conversion formula of logarithms,
logb1(X) = logb1(b2) * logb2(X)
=> logb2(X) = (logb1(X))/(logb1(b2))
Now we can just do this,
Digits = ⌊logb2(N!)⌋ + 1 = ⌊(log10(N!))/(log10(b2))⌋ + 1
To avoid repetition for calculation, we can do memoization in an array for log10(1) + log10(2) + ... + log10(106).
The above implementation is accepted
.
Caution : Remember to take digits
as an integer data type that can hold 106 but avoid floating points.
Solution in C
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
double memoizedArray[1000001];
memoizedArray[0] = 0;
for(int i=1;i<=1000000;i++){
memoizedArray[i] = memoizedArray[i-1] + log(i);
}
int testCase, base;
long digits,n;
cin >> testCase;
for(int i = 1; i<= testCase; i++){
cin >> n >> base;
digits = memoizedArray[n]/log(base) + 1;
cout << "Case " << i << ": " << digits << "\n";
}
return 0;
}
Tutorial source