Techniques to solve Problems LightOJ - 1045 , LightOJ - 1067 , LightOJ - 1090

In this article I am writing some of my techniques in describe which I have used to solved the following problems:

1. LightOJ - 1045 - Digits of Factorial
2. LightOJ - 1067 - Combinations
3. LightOJ - 1090 - Trailing Zeroes (II)

Please follow the above sequences one by one to get your desired problem.

1. LightOJ - 1045 - Digits of Factorial  

Technique: You know about finding the factorial of a number. If you don't know, then don't worry. I am here to help you on this. Suppose, I have to find the factorial of n which is denoted by n! . The law to calculate the factorial is,
n!= n* (n-1) * (n-2) * (n-3)...*1 .
For n=4 , n!=4!=4*3*2*1=24. 
I am forwarding to the solution but before it I am going to give you some basic on this so that my blog become helpful to the readers who are new at programming. If you know then skip them and go to the starred section. 
In this problem you are said to find the number of digits. In C++, you can at most use long long int data type which can store value upto approximately 10^18. But here , the number is at most 1000000. The factorial of that number is impossible to store in long long int data type. What should we do now??

Yes!! There is a way to handle this situation and this is the array manipulation. In this method you at first declare an array and every time store the multiplication result in the array. And multiply the number with the elements of the array. Google this topics to be clear. 

*** If we follow the above procedure, the inefficient implementation can leads you to the TLE verdict. Besides there is a factor of base conversion. One way could be that you calculate the factorial in decimal base then convert it to the desired base. But this work is teddy and inefficient implementation can leads to another TLE verdict. 
To handle this situation shortly there's an formula exist.

Q. How to find the number of digits in factorial of n of base b? 
Answer: 

1. At first Precalculate the logarithms of number 1 to n and add them all in an array, say, sum[n].
   sum[n]=log(1)+log(2)+....+log(n).
2. Now divide sum[n] by the log of b: log(b).
3. result= sum/log(b).
4. Add 1 to the result for final result.
5. Ans= result+1;
6. For any value of n you just need to divide sum[n] and you can get the result at O(1).

2. LightOJ - 1067 - Combinations 

 

Technique: This is a straight forward combination problem. The formula for calculating the combination is,
C(n,r)=n!/(r!*(n-r)!); --- (1)
Optimization can be done by another formula C(n,r)=C(n,n-r); 
   
So at the initial part of the problem solving we shall reduce the value of r to n-r. It is your choice or you can keep it. Now, What we have to do is precomputation to avoid time limit exceeded verdict. Since the resultant number could be very big!! So we have to mod this number every time we perform a multiplication. You can check my code at the bottom of this post for see how it works!
As sample, if we multiply a and b and perform mod on them then we can writ as below:
(a*b)%m = =(a%m * b%m)%m.
It is not that tough. After precomputation of all factorial of all number then we have got the value of n!,r! and (n-r)!. we can multiply r! & (n-r)!.
Now this is an important part. Suppose a=n! and b=r!*(n-r)!. Since the result could be very big so you have to perform mod operation on them which would be like (a/b)%m.

 We can perform modular multiplication, addition and subtraction easily but we can't perform modular division in the same way. So, We have to bring a new term Modular Multiplicative Inverse. That means we have find the modular multiplicative inverse of b with respect to m.  Let N is the modular multiplicative inverse of b with respect to m.

Then (a/b)%m would be like,
(a*N)%m = (a%m * N%m)%m.
Isn't is easy? 
OK. then try your self and if any problem then let me know.
     

3. LightOJ - 1090 - Trailing Zeroes (II)  

 

Technique: The problem is very interesting if you can enjoy. In this problem you are said to find the number of  trailing zeroes. You probably be known that multiplication of 2 & 5 can produce a zero. Multiplication by olny 2 or only 5 never can increase the number of zero.

For example, 
2*5=10.
6*2=12.
9*5=45.

Remember, if I multiply 12 by 5 then we can get a zero. This is because 12 can be written as the multiplication of 2 and hence there's 2 exist there. And 2 and 5 have produced  a zero.

For Example, 12*5=2*2*3*5=60 (a Zero).
So, If we check a number that how many times it is divided by 2 and 5 in common then, we easily can find the number of zeroes in that number.

Here, Given C(n,r)*p^q. Since the input number is very big so if we calculate the necessary calculation in every test case then we could get time limit exceeded verdict. What's the necessary of it? Let's bypass it. A way could be that we can precalculate the necessary calculation before and can use them after in every test cases. The result could be found in O(1). 

When finding the factorial of a number then to find how many zeroes could be present  in the result, you need to sum all the numbers of two and five you have got from 1 to that number. In my code at the bottom, you would see that I have stored them in pp[i][0] and pp[i][1]. 
I used these data when calculates C(n,r).
For p^q, you don't need any previous number instead of present number of two and five. So, I kept them simply in pp[i][2] and pp[i][3]. When using them, to handle the power q, I just have multiplied q with pp[i][2] and pp[i][3].

After performing above operations the final number of zeroes can be found.

Don't hesitate to comment.