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

• Logarithm - Britannica
• Logarithm - Wikipedia
• Memoization (1D, 2D and 3D) - Geeks for Geeks

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 log₁₀(X) :

But we need to determine the number of digits for N!. So, ⌊log₁₀(N!)⌋ + 1 will help us for base - 10.

For ⌊log₁₀(N!)⌋, if we recall the formula for log₁₀(X₁ * X₂ * X₃ * ... * X_n),

log₁₀(X₁ * X₂ * X₃ * ... * X_n) = log₁₀(X₁) + log₁₀(X₂) + log₁₀(X₃) + ... + log₁₀(X_n)

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,

log_b1(X) = log_b1(b2) * log_b2(X)

=> log_b2(X) = (log_b1(X))/(log_b1(b2))

Now we can just do this,

Digits = ⌊log_b2(N!)⌋ + 1 = ⌊(log₁₀(N!))/(log₁₀(b2))⌋ + 1

To avoid repetition for calculation, we can do memoization in an array for log₁₀(1) + log₁₀(2) + ... + log₁₀(10⁶).

The above implementation is accepted.

Caution : Remember to take digits as an integer data type that can hold 10⁶ 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];//Array for Memoization
    memoizedArray[0] = 0; //Don't do manual log for 0, it will throw an error

    //Memoizing the array
    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;
        //The formula
        digits = memoizedArray[n]/log(base) + 1;
        cout << "Case " << i << ": " << digits << "\n";
    }

    return 0;
}

Tutorial source