Problem

Given an integer $N$, find number of digits in $N!$.

For example, for $N=3$, number of digits in $N! = 3! = 3 \times 2 \times 1 = 6$ is $1$. For $N=5$, number of digits in $5! = 120$ is $3$.

Brute Force Solution

The first solution that pops into mind is to calculate $N!$ and count how many digits it has. A possible solution will look like the following:

int factorialDigit ( int n ) {
    long long fact = 1;
    for ( int i = 2; i <= n; i++ ) {
        fact *= i;
    }

    int res = 0; // Number of digit of n!
    while ( fact ) { //  Loop until fact becomes 0
        res++;
        fact /= 10; // Remove last digit
    }

    return res;
}

This code works, but only for $N \leq 20$. Once $N$ crosses $20$, it no longer fits in a "long long" variable.

Since the factorial of $N > 20$ overflows long long, how about we use "Big Integer" to store the value?

Brute Force Solution with Big Integer

If you don't know what Big Integer is, then know that it is a class for arbitrary large integer. C++ does not support this class so we will have to manually implement it if we want to use C++ to solve problems involving large integers. Or you could use a programming language that supports this class, such as Java.

I will write a post on Big Integer someday, but for now you could just use the Big Int class written by +Anudeep Nekkanti from here.

Multiplication of a Big Integer and an integer takes $O(\text{number of digits of Big Integer})$. Assuming that when calculating $N!$, the number of digits of $N!$ increases by $1$ at each step, it will take $O(N^2)$ time to compute $N!$. But obviously $N!$ does not increase by $1$ digit at each step ( for e.g, multiply by $100$ increases it by $2$ digits ), so worst time complexity is worse than $O(N^2)$.

Solution Using Logarithm

Logarithm of a number is connected to its number of digits, which might not be apparent. What is logarithm? Logarithm of a number $x$, in base $b$, is a real number $y$ such that $x = b^y$. For example:

$$log_{10}1234 = 3.0913151597 \text{ and } 10^{3.0913151597} = 1234$$

In logarithms, the base of the number is important. Since we want the number of digits of $N!$ in decimal, we will work with base $10$.

Number of Digit of an Integer

First, we will apply the logarithm idea on an integer. So where is the connection of logarithm with digit number? Look at the following logarithm values:

$log_{10}(x) = y$
$log_{10}(1) = 0$
$log_{10}(10) = 1$
$log_{10}(100 )= 2$
$log_{10}(1000) = 3$
$log_{10}(10000) = 4$

As the value of $x$ increases, the value of $y$ also increases. Every time we multiple $x$ by $10$, value of $y$ increases by $1$. That is every time number of digit increases, the value of $y$ increases. From this table, we can infer a few things about the log of other values.

If $log_{10}(100)$ is 2, and $log_{10}(1000)$ is 3, then for all value of $x$ where $100 < x < 1000$ , value of $y$ will lie between $2 < y < 3$. Let us try this out.

$log_{10}(100) = 2$
$log_{10}(150) = 2.17609125906$
$log_{10}(500) = 2.69897000434$
$log_{10}(999) = 2.99956548823$

Now note that, for every $100 \leq x < 1000$, value of $y$ is $2 \leq y < 3$. Can you see some relation between value of $y$ and number of digits of $x$?

Yes. If the value of $y$ is of the form $2.XXX$, then $x$ has $2+1=3$ digits.

$$\therefore \text{number of digits of}: x = \lfloor log_{10} (x) \rfloor + 1$$

Also note that, even though theoretically we just need to add 1 to $log_{10}(x)$ before flooring, it is good practice to add eps (where eps is a small value: $eps = 10^{-9})$ while we are at it. Why? Due to precision error, sometimes our program may say that $log_{10}(100) = 1.9999999$ instead of $2$. In order to avoid such scenes, we add eps to it before flooring.

int numberDigit ( int n ) {
    int wrongAnswer = log10(n) + 1; // This may give wrong answer sometimes.
    int rightAnswer = log10(n) + 1 + eps; // This is right.
    return rightAnswer;
}

If you are wondering, where is the floor function, know that in line $3$, we are assigning $log10(n) + 1 + eps$ to an integer. This has same action as $floor()$ function. Also note that we used $log10()$ function instead of $log()$ function. Unlike our calculators, in C++ $log()$ has base $2$.

Extending To Factorial

So how do we extend this idea to $N!$?

Let $x = log_{10}(N!)$. Then our answer will be $res = \lfloor x \rfloor + 1$. So all we need to do is find value of $x$.

$x = log_{10}(N!)$
$x = log_{10}(1 \times 2 \times 3 \times ... \times N)$
$\therefore x = log_{10}(1) + log_{10}(2) + log_{10}(3) + ... + log_{10}(N)$ This is using the law $log_{10}(ab) = log_{10}(a)+log_{10}(b)$

So in order to calculate $x = log_{10}(N!)$, we don't have to calculate value of $N!$. We can simply add log value of all numbers from $1$ to $N$. This can be achieved in $O(N)$.

int factorialDigit ( int n ) {
    double x = 0;
    for ( int i = 1; i <= n; i++ ) {
        x += log10 ( i );
    }
    int res = x + 1 + eps;
    return res;
}

Digits of $N!$ in Different Base

Now what if we want to find how many digits $N!$ has if we convert $N!$ to some other base.

For example, how many digits $3!$ has in the binary number system with base $2$? We know that $(6)_{10} = (110)_2$. So $3!$ has $3$ digits in base $2$ number system.

Can we use logarithms to solve this problem too? Yes.

$$\text{number of digits of x in base B} = \lfloor log_B(x) \rfloor + 1$$

All we need to do is change the base of our $log$ and it will find the number of digits in that base.

But, how do we change base in our code? We can only use log with base $2$ and $10$ in C++. Fear not, we can use the following law to change base of logartihm from $B$ to $C$.
$$log_B(x) = \frac{log_C(x)}{log_C(B)}$$
So in C++, we will use $C = 2$ or $C=10$ to find value of $log_B(x)$.

int factorialDigitExtended ( int n, int base ) {
    double x = 0;
    for ( int i = 1; i <= n; i++ ) {
        x += log10 ( i ) / log10(base); // Base Conversion
    }
    int res = x + 1 + eps;
    return res;
}

• Category: CPPS, Number Theory