You are not logged in. Please login at www.codechef.com to post your questions!

×

BIGO02-Editorial

Problem Link :

Practice
Contest

Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :

Simple

Pre-requisites :

Logarithm

Problem :

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

This question is marked "community wiki".

asked 03 Apr '15, 17:11

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

edited 03 Apr '15, 17:13

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,678
×1,173
×15
×7
×2

question asked: 03 Apr '15, 17:11

question was seen: 644 times

last updated: 03 Apr '15, 17:13