# 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 [1]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 [1], 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!$ ):

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

## Resource

- forthright48 - Number of Trailing Zeroes of Factorial

Would have been better if you gave the implementation of code

ReplyDeleteI added another comment above the function name in code. Hopefully, that will make things clearer. To find first 4 digits of 100! you just need to call the function: leadingDigitFact(100,4).

DeleteVaiya last 3 digit kibabe ber korbo

Delete@taslim uddin: Mod the factorial with 1000. It should give you the last 3 digits.

Delete