Saturday, August 8, 2015

Number of Digits of Factorial

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 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, base of the number is important. Since we want 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, 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, value of $y$ increases. From this table, we can infer few things about 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 form $2.XXX$, then $x$ has $2+1=3$ digits.  
$$\therefore \text{number of digits of}\: x = \lfloor log_{10} (x) \rfloor + 1$$
Be careful, $\lfloor log_{10} (x) \rfloor + 1$ is not same as $\lfloor log_{10} (x) + 1  \rfloor$. Try it out with $100,1000,10000$. We need to floor the log value before we add 1. 
int numberDigit ( int n ) {
    int wrongAnswer = log10(n) + 1; ///This is wrong.
    int rightAnswer = ( (int) log10(n) ) + 1; ///This is right.
    return rightAnswer;
}
In line $3$, we type cast $log10(n)$ to 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 = ( (int) x ) + 1;
    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 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} = log_B(x)$$
All we need to do is change the base of our $log$ and it will find 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 = ( (int) x ) + 1;
    return res;
}

4 comments:

  1. Nice article ... helped me a lot :-)

    ReplyDelete
  2. Thanks a lot for the article... Completely understood :)

    ReplyDelete
  3. Very Useful Article.... It will be Great Help to me if I find more article like this.

    ReplyDelete
  4. Very much helpful to understand the theory gradually, thanks !!

    ReplyDelete

Leave comments for Queries, Bugs and Hugs.