Computing Binomial Coefficients i.e C(n,k)

There are many problems where we have to compute C(n,k) i.e  ( (n!)/( (n-k)! *(k!) ) ).
However,
computing C(n, k) can be a challenge when n and/or  k are large. There are several tricks
like: Making k smaller (if k > n − k, then we set k = n − k) because n C k = n C (n−k) .
 During intermediate computations, we divide the numbers first before multiply it with the
 next number; or use BigInteger technique (last resort as BigInteger operations are slow).
But there is another method to which we all are familiar but don't actually remember .
We can use  Pascal’s Triangle, a triangular array of binomial coefficients. The leftmost and
rightmost entries at each row are always 1. The inner values are the sum of two values directly
 above it, as shown for row n = 5 below : The value of ith entry of line number n is C(n,i);

          1               n= 0
        1   1             n= 1
      1   2   1           n= 2
    1   3   3   1         n = 3
   1  4   6   4   1       n = 4
 1  5   10  10  5   1     n = 5

The value of ith entry of line number n is C(n,i).
The below given code implements the formation of the pascal's triangle using a 2D array of size n*n.
The time complexity is of O(n^2) ,  but it's better than the general method of computing C(n,k) using multiplication.

#include<iostream>
#include<stdio.h>
using namespace std;

void printPascal(int n)
{
  int arr[n][n];
  for (int line = 0; line <= n; line++)
  {
    // Every line has number of integers equal to line number
    for (int i = 0; i <= line; i++)
    {
      // First and last values in every row are 1
      if (line == i || i == 0)
           arr[line][i] = 1;
      else // Other values are sum of values just above and left of above
           arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
      printf("%d ", arr[line][i]);
    }
    printf("\n");
  }
}
int main()
{
  printPascal(5);
}
output :

1  
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 

See this  triangle for understanding the above given code.

After going through the above topic ,  go through this link , and  first try to solve this question using bit shift operator (<<) . Why are you getting wrong answer ? Try using pow() function.You would be getting correct answer . To know the difference  between pow(2,n ) and  1<<n , go through This Link

Thank you and keep coding :)

Bitset in STL and Algorithms for finding Prime numbers

Hello  Guys ,
   Let's talk about the mathematics used in coding contests , like checking for prime numbers, finding prime factors , LCM , GCD ,Factorials  e.t.c
In this post I will be talking about an easy method to check whether a number is prime or not . For this I will be using  the famous  algorithm " Sieve of Eratosthenes" invented by Eratosthenes of Alexandria.

Before moving further I would like you to know what is 'bitset' . If you are familiar with this , you can jump to the next topic .

A bitset stores bits (elements with only two possible values: 0 or 1 , i.e true or false ). It  is an array of bool but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only, so space taken by bitset bs is less than that of bool bs[N] and vector bs(N)  i.e  each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).
Due to this single bit , the operation performed on bitset is faster than that of array and vector . We can access the element of bitset just like an index of an array or vector . But there is a major difference between bitset and array .
bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices.

The following code explains most of the basic member functions of bitset and there usage :

#include<iostream>
#include<bitset>
#define M 32
using namespace std;
int main()
{

// default constructor initializes with all bits 0
    bitset<M> bset1;
     // bset2 is initialized with bits of 20
    bitset<M> bset2(20);

    // bset3 is initialized with bits of specified binary string
    bitset<M> bset3(string("1100"));

    // cout prints exact bits representation of bitset
    cout << bset1 << endl;  // 00000000000000000000000000000000
    cout << bset2 << endl;  // 00000000000000000000000000010100
    cout << bset3 << endl;  // 00000000000000000000000000001100
    cout << endl;

    // declaring set8 with capacity of 8 bits

    bitset<8> set8;    // 00000000

    // setting first bit (or 6th index)
    set8[1] = 1;    // 00000010
    set8[4] = set8[1];   //  00010010
    cout << set8 << endl;

    // count function returns number of set bits in bitset
    int numberof1 = set8.count();

    // size function returns total number of bits in bitset
    // so there difference will give us number of unset(0)
    // bits in bitset
    int numberof0 = set8.size() - numberof1;
    cout << set8 << " has " << numberof1 << " ones and "
         << numberof0 << " zeros\n";

    // test function return 1 if bit is set else returns 0
    cout << "bool representation of " << set8 << " : ";
    for (int i = 0; i < set8.size(); i++)
        cout << set8.test(i) << " ";

    cout << endl;

    // any function returns true, if atleast 1 bit
    // is set
    if (!set8.any())
        cout << "set8 has no bit set.\n";

    if (!bset1.any())
        cout << "bset1 has no bit set.\n";

    // none function returns true, if none of the bit
    // is set
    if (!bset1.none())
        cout << "bset1 has all bit set\n";

    // bset.set() sets all bits
    cout << set8.set() << endl;

    //  bset.set(pos, b) makes bset[pos] = b
    cout << set8.set(4, 0) << endl;

    // bset.set(pos) makes bset[pos] = 1  i.e. default
    // is 1
    cout << set8.set(4) << endl;

    // reset function makes all bits 0
    cout << set8.reset(2) << endl;
    cout << set8.reset() << endl;

    // flip function flips all bits i.e.  1 <-> 0
    // and  0 <-> 1
    cout << set8.flip(2) << endl;
    cout << set8.flip() << endl;

    // Converting decimal number to binary by using bitset
    int num = 100;
    cout  << "\nDecimal number: " << num
         << "  Binary equivalent: " << bitset<8>(num);
  cout<<endl;
    return 0;
}

Output :

00000000000000000000000000000000
00000000000000000000000000010100
00000000000000000000000000001100

00010010
00010010 has 2 ones and 6 zeros
bool representation of 00010010 : 0 1 0 0 1 0 0 0
bset1 has no bit set.
11111111
11101111
11111111
11111011
00000000
00000100
11111011

Decimal number: 100 Binary equivalent: 01100100


Now coming back to our initial discussion regarding  prime numbers :

First, this Sieve algorithm sets all numbers in the range to be ‘probably prime’ but set
numbers 0 and 1 to be not prime. Then, it takes 2 as prime and crosses out all multiples
of 2 starting from 2 × 2 = 4, 6, 8, 10, . . . until the multiple is greater than N. Then it takes
the next non-crossed number 3 as a prime and crosses out all multiples of 3 starting from
3 × 3 = 9, 12, 15, . . .. Then it takes 5 and crosses out all multiples of 5 starting from 5 × 5 =
25, 30, 35, . . .. And so on . . .. After that, whatever left uncrossed within the range [0..N]
are primes. This algorithm does approximately (N× (1/2 + 1/3 + 1/5 + 1/7 + . . . + 1/last
prime in range ≤ N)) operations. The time complexity is of roughly O(N log log N).
Generating a list of primes ≤ 10K using the sieve is fast , we opt to use sieve for smaller
 primes and for the larger prime numbers we use other methods which I will be discussing later .
 The code is as follows:

#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
long long int _sieve_size;
bitset<10000010> bs; // 10^7 should be enough for most cases
vector<long long int> primes; // compact list of primes in form of vector<int>

void sieve(long long int upperbound)
{  
  // create list of primes in [0..upperbound]
_sieve_size = upperbound + 1; // add 1 to include upperbound
bs.set(); // set all bits to 1
bs[0] = bs[1] = 0;// except index 0 and 1
for (long long int  i = 2; i <= _sieve_size; i++)
{
if (bs[i])
{
// cross out multiples of i starting from i * i!
for (long long int j = i * i; j <= _sieve_size; j += i)
{
bs[j] = 0;
}
primes.push_back((int)i);
// add this prime to the list of primes
}
}
}

bool isPrime(long long int N)
{
// a good enough deterministic prime tester
if (N <= _sieve_size) return bs[N];
// O(1) for small primes
cout<<(int)primes.size()<<endl;
for (int i = 0; i < (int)primes.size(); i++)

if (N % primes[i] == 0) return false;
return true;
// it takes longer time if N is a large prime!
}
// note: only work for N <= (last prime in vector  "primes")^2
// inside int main()
int main()
{


sieve(10000000);
// can go up to 10^7 (need few seconds)

printf("%d\n", isPrime(2147483647));
// 10-digits prime
printf("%d\n", isPrime(136117223861LL));
// not a prime, 104729*1299709
//How are we checking this for number which are > 10^7 ??
//Actually we cn check upto prime numbers < (10^7)^2!!! using this method
//because to check whether a number is prime number or not , all we need to check whether
// the number has any factor less than (number)^(0.5) or not

}

Thank you.Keep Coding :)