Problem Link :
Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu
Difficulty :
Simple
Pre-requisites :
LogarithmProblem :
The problem asked for finding the number of digits in x! where x is an integer input.
Explanation
If you know logarithm, then you can observe that
log (10) = 1;
log (100) = 2;
log(1000) = 3;
where base of logarithm is 10.
From this we can see that, for all x,
if x>=10 && x<100 , the result is greater than or equal to 1 but less than 2.
if x>=100 && x<1000 , the result is greater than or equal to 2 but less than 3.
if x>=1000 && x<10000 , the result is greater than or equal to 3 but less than 4.
and so on.
So typecasting the log(x) to integer gives one less than the number of digits in x.
So, log(x)+1 is the number of digits in x in decimal form.
N.B. This observation can be extended to any base. For integer x, log(x) base 2 gives number of
digits in x in its binary form. Similarly, log(x) base 3 gives number of digits in ternary form.
Now coming to the problem at hand, the result we need is log(x!)+1. Now, we can compute x! and
count the number of digits in it or apply log(x!)+1 to the resulting factorial. But this approach is very slow and will take a lot of time even in todays modern computers (If you are curious about how long a bruteforce approach will take, just try it).
We can use this property of logarithm here,
log(ab) = log (a) + log (b);
so, log(x!) = log(x) + log(x-1) + … +log(3) + log(2) + log(1);
Now the calculation won’t overflow and won’t take too much time to compute. Again, if we do this
calculation for every input, the number of calculations will be huge as well. So we can precompute the results and find the result for each number upto 1000000 and store it in an array, we can answer each query in O(1) time.
Don’t forget, we are adding the logarithms, not their typecasted values. We are typecasing only
when storing the value in array. Also, use long double to avoid floating point errors, if any. Take a look at setter’s solution to clarify any doubts.
N.B. If you solve it using any other methods, please share it in the comments.
Setter’s solution:
Can be found here