Useful Techniques to solve Problems LightOJ - 1054

I am here to describe some techniques which can help you solve the following problems:

1. LightOJ - 1054 - Efficient Pseudo Code 
2. LightOJ - 1098 - A New Function
3. LightOJ - 1215 - Finding LCM

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

1. LightOJ - 1054 - Efficient Pseudo Code 

Technique:  

     

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.

 

 

Techniques and Solutions of Problems LightOJ - 1007 , LightOJ - 1014, LightOJ - 1024 , LightOJ - 1028 , LightOJ - 1035

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

1. LightOJ - 1007 Mathematically Hard
2. LightOJ - 1014 Ifter Party
3. LightOJ - 1024 Eid
4. LightOJ - 1028 Trailing Zeroes (I)
5. LightOJ - 1035 Intelligent Factorial Factorization

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

1. LightOJ - 1007 Mathematically Hard

 

Technique: This is an exact application of Prime Numbers. In this problem just one variance is used and this is called Euler Phi. If you have no idea about Euler phi then please learn the basic from here. you should see that there is an equation which can find the number of relative prime smaller than a particular number.Say the number is n, then the Phi of n is defined as the number of relative prime smaller then n.

OK. We have just got the equation in above picture. There, P1, P2,...Pm are the primes that divides the number(n) and e1,e2,...,em are the exponent or the number of times a particular prime divides the number(n).
Since we have to multiply n hence we would multiply every number in the array by that line:
for(i=2;i<=5000000;i++) res1[i]=i; 
 
To solve this,  You need to first generate primes till the desired number. Then there is a technique which will help you to skip the time limit exceed verdicts. For every prime you just calculate its part for the numbers it divides.

2. LightOJ - 1014 Ifter Party    

 

Technique: Read carefully, you'll notice that P-L number piaju's are left. When no contestant can eat any piaju's then the case will be "impossible".
Now for possible case: There's no restriction in contestant number. It means that contestant number can be any value. You have to find the number of piaju's each contestant ate. So, each contestant can ate any number of piaju's which divides the P-L value. Suppore, if P-L is 4, then contestant can ate 1,2 or 4 piaju's each since they divides 4. Contestant can't ate 3 piaju's since it doesn't divides 4. So, we can divide P-L by all value less then P-L to check which value divides it and the value must be greater then L since it has been told that L<Q . 
An optimization is square root the P-L since dividing by the value of one site of square root value we could get the value of other site.

3. LightOJ - 1024 Eid  

 

Technique: This is a very interesting problem . I am describing it in a very simple straightforward way. Listen, You are given some de-sec. You are told to find such a de-sec (EID) in which all the races eat together. So, what you have understood?? You are given some number. Find the number which is divisible by all of them. Are you getting any coincidence among them. Yes!! This is a LCM,i mean, Longest Common Multiple problem. But, the problem is here you have to find the longest common multiple of maximum approximately 1000 numbers. So, the resultant number could be very big and overflow the long long int too. So, You need to do array manipulation. Did you know the prime factorization mathod to find LCM? This is necessary here. You can check my code below to understand the LCM procedure. But, Try yourself.

4. LightOJ - 1028 Trailing Zeroes (I)

 

Technique: Have you any idea about the finding the number of divisors of a number? This problem is a of that type. Here, Since you are said to find such a base in which trailing zeros exist so it can be assumed that if we can find the number of divisor of that number then the problem can be solved easily. Have you any idea? 
Suppose n is a number and its prime factorization is n=P1^x * P2^y. Then the number of divisors of n is = (x+1)*(y+1).
Suppose n=6, then 6= 2^1*3^1. Now, Number of divisor = (1+1)*(1+1)=4.
So, After prime generation just do this work and this is the result.

5. LightOJ - 1035 Intelligent Factorial Factorization

 

Technique: I Think you should get the technique to solve this problem yourself. You could have implementation problem. However, I am helping you in both case here. In this problem since you have to do prime factorization till N! (1,2,3,..,N) So, what you need to do extra is memorize the prime factorization of a number and add it with the factorization of next number till 1 to N. In my code, I did this.


If you have any problem understanding then leave a comment.

Prime Generation: Sieve of Eratosthenes Method and its Complexity analysis

This tutorial is the Second part of the Prime Number Tutorial. You can also check the previous tutorial on this prime number tutorial series.
Previous Tutorial Link: All about Prime numbers, from Introduction to Application including Generation

All about Prime numbers, from Introduction to Application including Generation

This is my first tutorial for this session. If you don’t know anything about prime number then don’t worry. Just read and practice carefully the tutorial below. I think after completing my tutorial you probably will be an expert in prime term.

If you know many thing about prime then just look down and don’t miss the complexity section.

I am dividing this tutorial in several sections as follows:

• Prime Introduction
• Prime Generation simple and less efficient and must know technique
• Practice section
• About next tutorial

Prime Introduction  

 
Q. What is Prime number?
Answer: A number (must be natural and positive) which is greater than 1 and has no divisor other than 1 and itself is called a prime number.
For example,  

• 2 is a prime number. Because it is greater than 1 and has no divisor other than 1 and 2 itself.
• 3 is a prime number. Because it is greater than 1 and has no divisor other than 1 and 3 itself.
• 6 is not a prime number. Because it is also divisible by 2 and 3 other than 1 and 6 itself. So, its not a prime number.

I think you are now clear about the basic prime number definition.

Prime Generation simple and less efficient and must know technique 

 
There are many ways to generate prime numbers. I shall describe two of this. One is here. And other is in another section in below.

Suppose, n is a number to test prime or not!!

As our definition say, A Prime number is divisible by only 1 and itself. So, we don’t need to check it by 1 and n. rather we shall check it by 2 to (n-1). If the number to test (n) is divisible by any of this number from 2 to (n-1) then it breaks the rule to be prime number and hence it is not a prime. But if it is not divisible by any number between 2 to (n-1) then it satisfy the rule to be prime number and hence it is a prime number.

For example,
Suppose n=5.
Then we shall check it by 2 to (n-1): 2,3,4.
For 2, n%2! =0, not divisible.
For 3, n%3! =0, not divisible.
For 4, n%4! =0, not divisible.
Here, n=5 is not divisible by any number from 2 to (n-1)=4. So, n=5 is a prime number.

Suppose n=6.
Then we shall check it by 2 to (n-1): 2,3,4,5.
For 2, n%2 ==0, divisible.
For 3, n%3 ==0, divisible.
For 4, n%4! =0, not divisible.
For 5, n%5! =0, not divisible.
Here, n=6 is divisible by 2 and 3 and it has divisors 2 and 3 rather than 1 and 6. So, n=6 is not a prime.

How to code:
It can be implemented using a single loop as like follows:

Suppose, We shall check for n !!!

int i,n;
for(i=2;i<=(n-1);i++)
{
 if(n%i==0)
 {

  printf(“It is divisible by a number rather than 1 and itself. So n is not a prime.”);

  break;
 }
}
if(i==n) printf(“It is not divisible by any number rather than 1 and itself. So n is a prime.”);

Several question and answer about the above code:

1. Q1. Here you may ask me a question that why I have used break statement when 'if (n%i==0)' condition is satisfied???
2. Q2. Why have you used the condition ’if(i==n)‘???

Answer Q1: (n%i==0) condition will only be satisfied if n is divisible by i. As we know, n will not be prime if it is divisible by any number without 1 and n, since n is divisible by I(any number) so n is not a prime number and I have got my answer.  So I don’t need to check n by others. So, I have broken the loop.

Answer Q2:  See, if n is divisible by any I, then it will satisfy the condition (n%i==0) and will execute the break statement that will break the for loop. But if n is not divisible by any I, then it not satisfy the condition (n%i==0) and will not break the loop. So, loop will be continuing until I reached to a value greater than (n-1). In this case, I will reach to the immediate value of (n-1) which is n.
So, if I can reach to n, then n is a prime number since no value from 2 to (n-1) can divide n. 

Practice section

I think you have learn the easiest procedure to generate prime very smartly. Now, Some task for you to practice:

1. Q1. Generate all primes from 1 to 100.
2. Q2. Check if 100 is a prime or not?
3. Q3. Generate all primes from 1 to 1000000.  

Answer Q1: 
The question is to generate all primes from 1 to 100. We can do this easily. I hope, reading the above part sincerely you can now easily generate a single prime number. Ok, this is enough for further processing :) . 
To generate prime from 1 to 100, you just need a for loop which will be run for 1 to 100. Now, Suppose 'i' is the variable which will count loop(loop counter) and also contain the number from 1 to 100. Now,  for every 'i' we just check that is this number is prime or not!!! If this is prime than we'll print it otherwise skip it. 
By definition 1 is not prime so we shall start from 2.
The pseudo-code can be as follow:

1. define i,j;
2. for i=2 to 100
     for j=2 to (i-1)
        if(i%j==0) then print: i is not prime
                     break;
        else continue the inner loop.
     if(i==j) then print: i is a prime number
     end for
3. end for

Answer Q2: 
This is also is a very common and easy. You just test for 100 and if it is prime then output that is is prime otherwise output this is not prime.
In the above pseudo-code you just need to cut the outer loop ant set the value of i equal to 100.
Please try yourself to code.

Answer Q3: 
This is same as the first question and answer is same if you replace 100 by 1000000. But why I make it separate question !!! This is one of the case where this method of prime generation is going to be slow and inefficient.
Since, people want something efficient so there's a new method of prime generation called famous Sieve of Eratosthenes method which I'll explain in the next tutorial of this session.

Practice Problem :

1. UVA 543 - Goldbach's Conjecture (Level One)

About next tutorial

Today I am very tired after writing this long tutorial. I shall explain this fantastic method in the next tutorial of this session. So, please stay in touch and comment if there's any bug in this tutorial.


Next Tutorial Link: Prime Generation: Sieve of Eratosthenes Method and its Complexity analysis


 H A P P Y   C O D I N G ! !! !!!