Light Oj : 1045 - Digits of Factorial

Here by  "log(b)(a)"  i mean  "b based log of a" .

We know that if   "a"   is a number , then  log(b)(a) represents the number of digits of  "a" assuming it
a  "b" based number .


Lets see an example of 5! where a=5 ----------------

we know  5! = (1*2*3*4*5)

So the number of digits in 5! = log( 5! ) = log(1*2*3*4*5) + 1 .

 ( "+1" for precision details at * marked line )

now question is : how can we calculate 1 to 1000000 number's factorial in O(n) time ?


log(1*2*3*4*5) =log1+log2+log3+log4+log5;

So now with the help of a double array we can save & propagate number of digits of each

number's(1,2,3,4,5) factorial .

double arra[1000000];

arra[0]=0.0;

for(int i=1;i<=1000001;i++)
{
      arra[i]=arra[i-1]+log10(i);
}

we know  from the formula of logarithm  that  log(b)(a) = ( log(x)(a) / log(x)(a) )  ;

where  x is any number which represents base .

after that at O(1) complexity  we can retrieve  answer = (ll) arra[a]/log10(b)  ;

here a 1 is to added up with answer  to remove precision value .