Some important mathematical concepts to know for Competitive Programming Problems

1. Finding nCr without factorial

20!=2432902008176640000,21!=51090942171709440000.Value upto 20! can be stored in long long data type(in C/C++,long in Java).After that answer goes beyond the range of long long data type.So, calculating nCr less than equal to 20! works with the normal approach but it fails for large values.

Therefore, we need another method for calculating nCr for factorial more than 20!

MATHEMATICAL CONCEPT(TRICK):

Done using basic knowledge of calculating GCD.

for example: N = 50 , R = 25

50C25 = 50!/(25! * (50-25)!)

Step 1: n=50,r=25

50/25(GCD(50,25)) = 25

So, divide both numbers by 25 we get, 2/1

Step 2: n=49,r=24

(49*2)/(24*1) = 98/24 (GCD(98,24)) = 2

So,divide both numbers by 2 we get, 49/12

Step 3: n=48,r=23

(48*49)/(23*12) = 2352/276 (GCD(2352,276)) = 12

So,divide both numbers by 12 we get,196/23

and so on.....This loop will run till r>0 and numerator value will be the answer.

CODE:

long nCr(int n,int r)

{
  long ans=1, den=1;

  if(r!=0)

  {

     while(r>0){

       ans = ans*n;

       den = den*r;

       long gcd = gcdFun(ans,den);

       ans = ans/gcd;

       den = den/gcd;

       n--;

       r--;

      }

   }

  else{

     ans = 1;

  }

return ans;


}

2. Fastest Way of finding Prime Numbers - Sieve of Eratosthenes

Prime Number - Positive integer that is divisible by 1 and itself.

for example:2,3,5,7,11,13,17

1. Naive Approach:for checking whether number is prime or not

CODE:

bool isPrime(int n){

if(n == 1)

return false;

if(n == 2)

return true;

for(int i=2;i<n;i++){

 if(n%i == 0){

   return false;

 }

}

return true;

}

TIME COMPLEXITY: O(n)

2. Seive Approach: Generate an array containing Prime Numbers

  MATHEMATICAL CONCEPT(TRICK):

  1. Create a boolean array prime[0....n] and initialize all entries as true. 

  2. A value in prime[i] will finally be false if i is not a Prime Number otherwise it will remain true.

  3. If prime[p] is not changed,means it is true,means it is prime, then update/mark all multiples of p as false.

  4. Finally,for those values which are true are prime numbers.

CODE:

Print all prime number less than or equal to n.

void SeiveApproach(int n){

boolean prime[] = new boolean[n+1];

for(int i=0;i<n;i++)

prime[i] = true;

for(int i=2;i*i<=n;i++){

// i is prime

   if(prime[i] == true)

   {

       // Update all multiples of i as Non-prime

          for(int j=i*i;j<=n;j=j+i)

          {

              prime[j] = false;

          }

    }

}

for(int i=2;i<=n;i++){

   if(prime[i]==true){

     System.out.println(i+" ");

    }

  }

}

TIME COMPLEXITY: O(n*log(log(n)))

3. Finding of trailing zero's in a factorial

 Input : n = 5

Output : 1

Factorial of 5 = 5 * 4 * 3 * 2 * 1 = 120 which has 1 trailing zero.

MATHMATICAL CONCEPT(TRICK):

Trailing zero's in n! = Count of 5s in prime factor of n! = floor(n/5) + floor(n/25) + floor(n/125) + .......

CODE:

static int NumTrailingZeros(int n){

int count = 0;

for(int i=5;n/i>=1;i*=5){

count+=n/i;

}

return count;


}