Prime Numbers by Sieve of Eratosthenes

The algorithm works as follows.
1. Create a vector v of consecutive integers {2,3,…,LIMIT}.
2. Select p as the first prime number in the vector v, p=2.
3. Remove all multiples of p from the vector v.
4. set p equal to the next integer in vector v which has not been removed.
5. Repeat steps 3 and 4 until p2 > LIMIT, all the remaining numbers in the vector v are prime numbers

More about the algorithm here.

Here’s the c++ code for the algorithm



vector<int> seive(int LIMIT){
    vector<bool> primes(LIMIT, false);
    primes[0]=true;//0 is not prime
    primes[1]=true;//1 is not prime
    int upperSqrt = (int) sqrt(LIMIT);

    for(int i = 2; i <= upperSqrt; i++){
        if (primes[i] == false){
            for (int j = i*i; j <= LIMIT; j+=i){
                primes[j] = true;
            }//end for j
        }//end if
    }//end for i

    vector<int> ret;//vector for holding only prime numbers

    REP(i,primes.size()){
        if(!primes[i]){
            ret.push_back(i);
        }
    }

    return ret;
}


Advertisements

Catalan Numbers

Catalan numbers form a sequence of natural numbers that occur in various counting problems.
Series is
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452…. and so on.
Application

This sequence is very popular in many combinatorial problems.  More on application of Catalan Numbers here

Formula

The nth Catalan number is given directly in terms of binomial coefficients by

Cn = 2nCn/(n+1) = 2n!/{(n+1)!n!}

we can also use this formula
C0 = 1
Cn = Cn-1*(4n-2)/(n+1)


cat=[]

#1st term is 1
cat.append(1)

for i in range (1,1001):
    x=cat[i-1]*(4*i-2)/(i+1)
    cat.append(x)


def CatalanNumber(n):
    return cat[n]

N numbers into 2N places

Question:

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly n number of cells between two placed locations of number n.

Sample:

One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

Solution:

We will try backtracking approach,  we move from index 0 to 2N-1, at each index, we try to place a number that hasn’t been used, and then move to next index and repeat the process, if in between we find there is no number possible at some index, that means we were incorrect, and we need to backtrack. If we reach to last index, and place a number safely there, that means its possible to have such arrangement.

#include<iostream>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cstring>
using namespace std;

#define FOR(i,a,b)      for(__typeof(b) i=(a);i<(b);++i)
#define REP(i,n)        for(__typeof(n) i=0;i<(n);i++)
#define FILL(a,b)       memset(a,b,sizeof(a))

#define SIZE 100
int N,len;
int arr[SIZE];
bool numbers[SIZE];

bool permute(int pos){
    /*if pos>=len , that means we have placed all the numbers
    from 1 to N , so we can print the array, and return
    */
    if(pos>=len){
        //nothing fancy, just printing the array
        printf("POSSIBLE for N = %d ----> ",N);
        REP(i,len){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        return true;
    }
    //if that position is already filled, that means move on 😛
    if(arr[pos]!=0){
        return permute(pos+1);
    }

    //go through all numbers
    FOR(i,1,N+1){
        //if number is not used
        if(!numbers[i]){
            //if second place is in bound
            if(pos+i+1<len&&!arr[pos]&&!arr[pos+i+1]){
                arr[pos]=i;//place the number i at index pos
                arr[pos+i+1]=i;//place the number i at index pos+i+1
                numbers[i]=true;//number i used now
                //check if this will lead us to end
                if(permute(pos+1)){
                    return true;
                }
                //BACKTRACK
                arr[pos]=0;//free the index pos
                arr[pos+i+1]=0;//free the index pos+i+1
                numbers[i]=false;//number not used now
            }
        }
    }
    return false;
}

void doThis(){
    //N number
    scanf("%d",&N);
    // 2N places
    len = 2*N;
    //initialise array with 0
    FILL(arr,0);
    FILL(numbers,false);//all numbers are free to be used

    //here we go
    if(permute(0)){
        //if possible then no need to do anything 🙂
    }else{
        printf("NOT POSSIBLE for N = %d\n",N);
    }
}

int main(){
#ifdef amy
freopen("C:\\A\\in.txt","r",stdin);freopen("C:\\A\\out.txt","w",stdout);
#endif
int t;
scanf("%d",&t);//number of test cases
while(t--){doThis();}
#ifdef amy
fprintf(stdout,"\nTIME: %.3lf sec\n",(double)clock()/(CLOCKS_PER_SEC));
#endif
return 0;
}

/*
INPUT

12
1
2
3
4
5
6
7
8
9
10
11
12

OUTPUT

NOT POSSIBLE for N = 1
NOT POSSIBLE for N = 2
POSSIBLE for N = 3 ----> 2 3 1 2 1 3
POSSIBLE for N = 4 ----> 2 3 4 2 1 3 1 4
NOT POSSIBLE for N = 5
NOT POSSIBLE for N = 6
POSSIBLE for N = 7 ----> 1 4 1 5 6 7 4 2 3 5 2 6 3 7
POSSIBLE for N = 8 ----> 1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8
NOT POSSIBLE for N = 9
NOT POSSIBLE for N = 10
POSSIBLE for N = 11 ----> 1 2 1 4 2 8 9 10 4 11 6 3 7 5 8 3 9 6 10 5 7 11
POSSIBLE for N = 12 ----> 1 2 1 3 2 8 9 3 10 11 12 5 7 4 8 6 9 5 4 10 7 11 6 12

TIME: 0.069 sec
*/

Morris InOrder Tree Traversal, Tree Traversal without using extra space and without recursion

We have the regular tree traversals that uses either recursion (function stack), or intentionally created stack to do the traversal in iterative way. But what do we do when we need to do a tree traversal without any extra space and without recursion.
Lets first think this way, iterative way is possible if we create a stack (this is a regular way). If we give some thought, we need stack for storing the in-order successor, we push the current node into stack and move to left, when we come back , we pop this node and print, and then move right.
Can we think of getting to this node back by some way. Does Threaded Binary Tree ring any bells? Yes, we can create threads back to the in-order successor, and in this way we will get to use the space (null pointers) of leaf nodes, and wont be needing any extra space.

So, Morris InOrder Traversal uses Threads instead of stack to get to the in-order successor. In this traversal, we first create threads to in-order successor, and print the nodes, and by the end we revert back the changes made to tree, i.e we remove all the additional threads we created in the process. Point to be noted is that, tree is modified in between, but by the end of traversal, original tree is restored.

Algorithm:
take root node into new node temp
while temp is not null
   if temp does not have left child
       print temp data
       move to right
   else
       Make temp as right child of the rightmost node in temp's left subtree 
       move to left

Here’s the C++ code

//Binary Tree
typedef struct bTree{
    int data;
    bTree *left,*right;
}bTree;
//MORRIS INORDER TRAVERSAL, pass the root node as argument
void morris(bTree *ptr){
    //testing part :P
    if(!ptr){
        return;
    }
    // we do have a genuine bTree

    bTree *temp;//temp pointer

    //loop till ptr is null
    while(ptr){
        // if ptr left is null
        if(!ptr->left){
            //print the data
            printf("[%d]",ptr->data);
            //move right
            ptr=ptr->right;
        }else{//has a left pointer

            //Find the inorder predecessor of current node
            temp = ptr->left;
            while(temp->right && temp->right!=ptr){
                temp=temp->right;
            }

            //Make current node as right child of its inorder predecessor
            if(!temp->right){
                temp->right=ptr;
                ptr=ptr->left;
            }else{
                // Revert the changes to restore the original tree
                temp->right = NULL;//make it the way it was earlier, i.e null
                printf("[%d]",ptr->data);
                ptr=ptr->right;
            }

        }//end if else
    }//end while
}//end func morris

Water Jug Problem

Question:

Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the  number of steps required to obtain exactly c liters of water in one of the vessels. You have infinite supply of water.

At the beginning both vessels are empty. The following operations are counted as ‘steps’:

  • emptying a vessel,
  • filling a vessel,
  • pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

Lets try solving it

Before calculating  steps, lets check what can we say if its possible or not given the values of a, b and c.
Its not possible if c > a and c > b, because then we are not having a vessel capable of holding c liters of water.
Its also not possible when c is not a multiple of hcf of a and b, because in that case we wont be able to make c liters ever.

Once its clear if its possible or not calculating minimum number of steps is easy.
If its possible then there are always 2 ways to do it, may be with different number of steps. What we do is, we recursively fill one bucket lets say a and empty it in b, and when b is full in between the process, we empty it, and again pour from a, and do this till the time we have c liters of water in either a or b, or both depending upon condition c < capacity of that vessel.
Second way would be to begin with b first. We will fill vessel b first , and start emptying it in a, and in case a is full in between we will empty a , and again pour water from b into a.

Example

Lets say we have 3 liters vessel A and 5 liters vessel B and we want to store 4 liters water C

Checking if its possible or not:
we can easily see 4 < 5 and also 4 is multiple of 1 (HCF of 5 and 3)

Lets try and fill 4 liters of water

Way 1.
We will repeatedly fill A and pour it in B
A = 3 and B = 5
                   Vessel A            Vessel B         Steps
initially              0                  0               0
Fill A                 3                  0               1
Pour A in B            0                  3               2
Fill A again           3                  3               3
Pour A in B            1                  5               4
Empty B                1                  0               5
Pour A in B            0                  1               6
Fill A                 3                  1               7
Pour A in B            0                  4               8
So we have 4 liters in B by way 1 in 8 steps.

Way 2.
We will repeatedly fill B and pour it in A
A = 3 and B = 5
                   Vessel A            Vessel B         Steps
initially              0                  0               0
Fill B                 0                  5               1
Pour B in A            3                  2               2
Empty A                0                  2               3
Pour B in A            2                  0               4
Fill B                 2                  5               5
Pour B in A            3                  4               6
So we have 4 liters in B by way 2 in 6 steps.

Here’s the piece of C++ code for checking and calculating the number of steps required.


/*
checking if its possible to fill C liters of water
in either of two vessels of capacity a and b with
infinite supply of water.
*/
bool check(int a,int b,int c){
    //boundary cases
    if(c>a && c>b)){
        return false;
    }
    //if c is multiple of HCF of a and b, then possible
    if(c%gcd(a,b)==0){
        return true;
    }
    //if c is not multiple of HCF of a and b, then not possible
    return false;
}

/*
calculating steps
Method:  Start filling A and pouring it in B,
in case B is full in between empty it, and
again pour from A, and repeat the process.
*/
int steps(int A,int B,int C){
    int steps = 0;
    int capacityA = A;
	int capacityB = B;
	int temp;
	//starting with empty buckets
    A= 0;
    B= 0;
    //repeating till either one of A and B has C liters of water
    while(A!=C && B!= C){
        //if A is empty, Fill A by supply of water
        if(A==0){
            A = capacityA;
            steps+=1;
        }else if(B==capacityB){
            //If B is full, in between the processempty it

            B=0;
            steps+=1;
        }else{
            /*
            Else, pour from A to B
            amount of water to be poured depends on how much B can hold
            which would be volume left in B or capacity of A, whichever is less
            */
            temp = min(capacityB-B,A);
            B+=temp;
            A-=temp;
            steps+=1;
        }

    }
    return  steps;
}

log(n) exponentiation

Main idea behind this is
Be=B if e = 1
Be=B*Be-1 if e is odd
Be=X2 where X = Be/2 if e is even

Here’s the python code for the same.

#calculating x^n
def logNexp(x,n):
    #base conditions
    if n == 0:
        return 1
    if n == 1:
        return x

    #holding x in case n is odd
    temp = x

    x = logNexp(x,n>>1)
    x = x*x

    #if n is odd
    if (n&1):
        x = temp*x

    return x

you can try other variations also, check this at wiki

Solving linear recurrence relations using Matrix Exponentiation

Many of us must be familiar with linear recurrences, its one of the frequent topics that come up in computer science and  programming contests. One of the classic problem is finding the nth term in Fibonacci sequence. Using recurrence relation and dynamic programming we can calculate the nth term in O(n) time. But many times n is very large  (of the order > 1010) that we need to calculate the nth in O(log n) time. This is where Matrix Exponentiation comes in handy.  All linear recurrences can be converted to matrices with sufficiently large dimensions.

Linear recurrences
A linear recurrence is a sequence in which each term (apart from few initial ones) is linear combination of previous terms.
Well know example is Fibonacci sequence
f(i)=f(i-1)+f(i-2) 
Another example is Tribonacci sequence
f(i)=f(i-1)+f(i-2)+f(i-3)

Fibonacci sequence is already very popular by itself, we will take tribionacci sequence for understanding the concepts.

Solving the problem (Tribonacci sequence)
First get the initial terms that are free from recurrence, or initial values as few may put it.
for Tribonacci sequence
f(0)=0
f(1)=0
f(2)=1
and for all i > 2,
we have the recurrence f(i)=f(i-1)+f(i-2)+f(i-3)
Lets call a constant K ,where k is the number of previous terms ith term is dependent on, like here K = 3.
Defining column vector Fi as a K x 1 matrix whose first row is f(i), second row is f(i+1), and so on, until K-th row is f(i+K-1). The initial values of f are given in column vector F1 that has values f(1) through f(K):

            
            |  f(0)    |
            |  f(1)    |
      F(1)= | ......   | 
            | ......   |
            |  f(k-1)  |

For Tribonacci sequence

            |   0    |
      F(1)= |   0    |
            |   1    |

now what we are interested in is this relation Fi+1 = M Fi  for some constant matrix M.
So our aim is to find this constant matrix M, for a given recurrence relation.

For a recurrence relation where the next term is dependent on last K terms, Fi+1 and Fi are matrices of size 1 x K and M is a matrix of size K x K.

| f(n+1)   |       | f(n)   |
|  f(n)    |       | f(n-1) |
| f(n-1)   | = M x | f(n-2) |
| ......   |       | ...... |
| f(n-K+1) |       | f(n-K) |

Lets check these things for tribonacci sequence.
Relation is f(i)=f(i-1)+f(i-2)+f(i-3)

| f(n+1)   |       | f(n)   |
|  f(n)    | = M x | f(n-1) |
| f(n-1)   |       | f(n-2) |

Now we know that M is a 3 x 3 matrix, so

| f(n+1) | = | a b c | x | f(n)   |
| f(n)   |   | d e f |   | f(n-1) |
| f(n-1) |   | g h i |   | f(n-2) |

We need to find the values of these unknown constants in matrix M,
so the series is 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504……..
we have 3 equations
f(n+1) = a*f(n)+b*f(n-1)+c*f(n-2)…………….eq 1
f(n)   = d*f(n)+e*f(n-1)+f*f(n-2)…………….eq 2
f(n-1)  = g*f(n)+h*f(n-1)+i*f(n-2)……………eq 3

suppose we take value of n = 2 in eq 1
we have f(3) = a*f(2)+b*f(1)+c*f(0)
by putting few initial terms of series together manually
f(0)=0, f(1)=0, f(2)=1, f(3)=1
solving, it gives a = 1.
Similarly we can carefully take values of n so that we can calculate the values of unknowns.
we can easily come up with value of matrix M

| f(n+1) | = | 1 1 1 | x | f(n)   |
| f(n)   |   | 1 0 0 |   | f(n-1) |
| f(n-1) |   | 0 1 0 |   | f(n-2) |

Now that we have got our matrix M, its just fun to find the nth term.
F2 = M F1
F3 = M F2=M2F1
and like this..
Fn = Mn-1 F1

our answer would be Fn[0]
So all we need now is to find the matrix Mn-1 to find the nth term.
The most popular method is to use exponentiation by squaring method that works in O(log N) time, with this recurrence:
Be=B if e = 1
Be=B*Be-1 if e is odd
Be=X2 where X = Be/2 if e is even
The multiplication part takes the O(K3) time and hence the overall complexity is O(K3 log n).

Here’s the source code for finding the nth term of Tribonacci sequence.
For the purpose of convenience, it would be nth term modulo 109+7

/* Amrendra Kumar */
#include<iostream>
#include<cmath>
#include<algorithm>
#include<climits>
#include<vector>
#include<cstdio>
#include<ctime>

using namespace std;
#define MOD 	 1000000007LL
#define LL 		 long long

#define FORD(i,a,b,d)   for(__typeof(b) i=(a);i<(b);i+=(d))
#define FOR(i,a,b)      for(__typeof(b) i=(a);i<(b);++i)
#define FORE(i,a,b)     for(__typeof(b) i=(a);i<=(b);++i)
#define REP(i,n)        for(__typeof(n) i=0;i<(n);i++)
#define FORR(i,n,e)     for(__typeof(n) i=(n);i>=(e);--i)
#define FORRD(i,n,e,d)  for(__typeof(n) i=(n);i>=(e);i-=(d))
#define FORI(it,s) 	    for(__typeof((s).begin()) (it)=(s).begin();(it)!=(s).end();(it)++)

//template can be used for multiplying the matrix.

//for multiplying the two 3*3 matrix
void multiplyMM(LL F[3][3], LL M[3][3]){
    LL l[3][3];
    l[0][0]=((F[0][0]*M[0][0])%MOD+(F[0][1]*M[1][0])%MOD+(F[0][2]*M[2][0])%MOD)%MOD;
    l[0][1]=((F[0][0]*M[0][1])%MOD+(F[0][1]*M[1][1])%MOD+(F[0][2]*M[2][1])%MOD)%MOD;
    l[0][2]=((F[0][0]*M[0][2])%MOD+(F[0][1]*M[1][2])%MOD+(F[0][2]*M[2][2])%MOD)%MOD;
    l[1][0]=((F[1][0]*M[0][0])%MOD+(F[1][1]*M[1][0])%MOD+(F[1][2]*M[2][0])%MOD)%MOD;
    l[1][1]=((F[1][0]*M[0][1])%MOD+(F[1][1]*M[1][1])%MOD+(F[1][2]*M[2][1])%MOD)%MOD;
    l[1][2]=((F[1][0]*M[0][2])%MOD+(F[1][1]*M[1][2])%MOD+(F[1][2]*M[2][2])%MOD)%MOD;
    l[2][0]=((F[2][0]*M[0][0])%MOD+(F[2][1]*M[1][0])%MOD+(F[2][2]*M[2][0])%MOD)%MOD;
    l[2][1]=((F[2][0]*M[0][1])%MOD+(F[2][1]*M[1][1])%MOD+(F[2][2]*M[2][1])%MOD)%MOD;
    l[2][2]=((F[2][0]*M[0][2])%MOD+(F[2][1]*M[1][2])%MOD+(F[2][2]*M[2][2])%MOD)%MOD;
    FOR(i,0,3){
        FOR(j,0,3){
            F[i][j]=l[i][j];
        }
    }
}

/*
DONT worry about the modulo thing, its just that I used the same code at CodeChef,
so a bit untidy, but I hope you'll get the concept
*/

//for multiplying the 1*3 and 3*3  matrix
void multiplyMF(LL m[3][3],LL a[3]){
    LL x = ((a[0]*m[0][0])%MOD + ((a[1]*m[0][1])%MOD)+ ((a[2]*m[0][2])%MOD))%MOD;
    LL y = ((a[0]*m[1][0])%MOD + ((a[1]*m[1][1])%MOD)+ ((a[2]*m[1][2])%MOD))%MOD;
    LL z = ((a[0]*m[2][0])%MOD + ((a[1]*m[2][1])%MOD)+ ((a[2]*m[2][2])%MOD))%MOD;
    a[0]=x;
    a[1]=y;
    a[2]=z;

}

//exponentiation by squaring method
void powerM(LL f[3][3],LL n){
    if(n==0||n==1||n<0){
        return;
    }
    LL M[3][3]={{1,1,1},{1,0,0},{0,1,0}};

    powerM(f, n/2);
    multiplyMM(f,f);

    if( n%2 != 0 )
     multiplyMM(f, M);

}

//main function for calculating the n-th tribonacci number
LL tribonacci(LL n){
    //then taking the f(1) column vector of initial values
    LL f[3]={0,0,1};

    if(n<3){//handling initial values
        return f[n];
    }

    //taking the matrix M
    LL M[3][3]={{1,1,1},{1,0,0},{0,1,0}};
    //calculating M^(n-1)
    powerM(M,n-1);

    //multiplying (M^n-1)*column vector
    multiplyMF(M,f);
    return(f[0]);

}

LL N;
void doThis(){
    scanf("%lld",&N);//scanf and printf are faster than cin and cout
    printf("%lld-->%lld\n",N,tribonacci(N));

}

int main(){
#ifdef amy
freopen("C:\\A\\in.txt","r",stdin);freopen("C:\\A\\out.txt","w",stdout);
#endif
int t;
scanf("%d",&t);//for number of test cases
while(t--){doThis();}
#ifdef amy
fprintf(stdout,"\nTIME: %.3lf sec\n",(double)clock()/(CLOCKS_PER_SEC));
#endif
return 0;
}

/*
INPUT:

21
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

OUTPUT:

0-->0
1-->0
2-->1
3-->1
4-->2
5-->4
6-->7
7-->13
8-->24
9-->44
10-->81
11-->149
12-->274
13-->504
14-->927
15-->1705
16-->3136
17-->5768
18-->10609
19-->19513
20-->35890

TIME: 0.002 sec

*/

We may have variations in the linear recurrence relation, but then we can carefully construct our constant matrix M.