Problem

Given an integer $N$, find the first $K$ leading digits of $N!$.

For example, for $N=10$ and $K=3$, then first $3$ leading digits of $10! = 3628800$ is $362$.

Finding leading digits uses concepts similar to [ref1] Number of Trailing Zeroes of Factorial.

Brute Force Solution

Finding the value of $N!$ and then printing the first $K$ digits is a simple but slow solution. Using long long we can calculate value $N!$ up to $N \leq 20$ and using Big Integer we can calculate arbitrary $N!$ but with complexity worse than $O(N^2)$.

Solution Using Logarithm

In [ref1], we say that a logarithm of value $x$ is $y$ such that $x = 10^y$. For now let us find out leading digits of a value $x$ instead of $N!$. We will extend it to cover factorials later.

So, we know that $log_{10}(x) = y$, where $y$ will be some fraction. Let us separate $y$ into its integer and decimal part and call them $p,q$. For example, if $y = 123.456$, then $p=123$ and $q=0.456$.

Therefore, we can say that $log_{10}(x) = p + q$. Which means, $x = 10^y = 10^{p+q}=10^p \times 10^q$.

Now expand the values of $10^p$ and $10^q$. If $A=10^p$, then $A$ will simply be a power of $10$ since $p$ is an integer. To be more exact, $A$ will be $1$ with $p$ trailing zeroes. For example, $A=10^3 = 1000$. What about $B=10^q$?

Since $q$ is a fraction which is $0 \leq q < 1$, value of $B$ will be between $10^0 \leq B < 10^1$, that is, $1 \leq B < 10$.

Okay, we got the value of $A$ and $B$, what now? We know that if we multiply $A$ and $B$ we will get $x$. But don’t multiply them just yet. Think for a bit what will happen when we multiply a decimal number with $10$. If it is integer, it will get a trailing zero, e.g, $3 \times 10 = 30$. But if it is a fraction, its decimal point will shift to right, e.g $23.65 \times 10 = 236.5$. Actually, decimal points shifts for integer numbers too, since integer numbers are real numbers with $0$ as fraction, e.g $3 = 3.00$. So in either case multiplying $10$ shifts decimal point to the right.

So what happens if we multiply, $A$, which is just $10^p$ to $B$? Since $A$ has $10$ in it $p$ times, the decimal point of $B$ will shift to right $p$ times. That is all $A$ does to $B$ is change its decimal point. It does not change the digits of $B$ in any way. Thus, $B$ contains all the leading digits of $x$.

For example,
$log_{10}(5420) = 3.7339993 = 3 + 0.7339993$.
$\therefore B = 10^0.7339993 = 5.4200$.

So, if we need first $K$ leading digits of $x$, we just need to multiply $B$ with $10^{K-1}$ and then throw away the fraction part. That is $res = \lfloor B \times 10^{K-1} \rfloor$. Why $10^{K-1}$ not just $10^K$? That’s because we already have $1$ leading digit present in $10^q$ before shifting it.

Extending to Factorial

It is easy to extend the idea above to $N!$. First we need to find out the value of $y=log_{10}(N!)$.

$y= log_{10}(N!)$
$y= log_{10}(N \times (N-1) \times (N-2) \times… \times 3 \times 2 \times 1 )$
$y= log_{10}(N) + log_{10}(N-1) + log_{10}(N-2) + … + log_{10}(2) + log_{10}(1)$

So we can simply find out the value of $y$ by running a loop from $1$ to $N$ and taking its log value.

After that we decompose $y$ into $p$, integer part and $q$, fraction part. The answer will be $\lfloor 10^q \times 10^{K-1}\rfloor$.

Code

const double eps = 1e-9;

// Find the first K digits of N!
int leadingDigitFact ( int n, int k ) {
    double fact = 0;

    // Find log(N!)
    for ( int i = 1; i <= n; i++ ) {
        fact += log10 ( i );
    }

    // Find the value of q
    double q = fact - floor ( fact+eps );

    double B = pow ( 10, q );

    // Shift decimal point k-1 \times
    for ( int i = 0; i < k - 1; i++ ) {
        B *= 10;
    }

    // Don't forget to floor it
    return floor(B+eps);
}

The code does exactly what we discussed before. But note the $eps$ that we added when flooring value in line $12$ and $22$. This due to precision error when dealing with real numbers in C++. For example, due to precision error sometimes a value which is supposed to be $1$, becomes $0.9999999999999$. The difference between these two values is very small, but if we floor them both, the first one becomes $1$ whereas the second one becomes $0$. So in order to avoid this error, when flooring a positive value we add a small number ( epsilon = $0.000000001$ ) to the number.

Summary

We need to execute the following steps to find the first $K$ leading digits of a number $x$ ( in our problem $x=N!$ ):

1. Find the log value of the number whose leading digits we are seeking. $y=log_{10}(x)$.
2. Decompose $y$ into two parts. Integer part $p$ and fraction part $q$.
3. The answer is $\lfloor 10^q \times 10^{K-1} \rfloor$.

Resource

1. forthright48 - Number of Trailing Zeroes of Factorial

• Category: CPPS, Number Theory