Segment Tree Source Code

Tutorial : http://www.shafaetsplanet.com/planetcoding/?p=1557


#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];


void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node]=tree[left]+tree[right];


}

int query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e) return 0;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);

    return p1+p2;
}

void update(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return;

    if(b==e)
    {
        tree[node]=val;
        return;
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}

int main()
{
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
    }

    init(1,1,n);

    cout<<query(1,1,n,3,7)<<endl;
    update(1, 1, n, 2, 2);
    cout << query(1, 1, n, 1, 2) << endl;
}

KMP source code 1

Tutorial :

1. https://tanvir002700.wordpress.com/2015/03/03/kmp-knuth-morris-pratt-algorithm/#more-556

2. https://returnzerooo.wordpress.com/2016/09/08/kmp/

3. https://www.youtube.com/watch?v=GTJr8OvyEVQ

4. https://www.youtube.com/watch?v=KG44VoDtsAA



source code :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{
   string text,pattern;

   cin>>text>>pattern;

    kmp_preprocess(pattern);

    bool n;

    n=kmp(text,pattern);

    cout<<n;

}

Bigmod recursive method source code

Tutorial Link : http://blog.forthright48.com/2015/08/modular-exponentiation.htm

Code :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int bigmod(ll int b,ll int p,ll int m)
{
    if(p==0) return 1%m;

    else if(p%2==0)
    {
        ll int y= bigmod(b,p/2,m);

        return (y*y)%m;
    }
    else return (b*(bigmod(b,p-1,m)))%m;
}

int main()
{
 ll int b,p,m;

 scanf("%lld%lld%lld",&b,&p,&m);

 printf("%lld",bigmod(b,p,m));


}

Factorial Finding Source code

Tutorial Link : http://www.geeksforgeeks.org/factorial-large-number/

Source Code :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

#define MAX 800

ll int multiply(ll int x,ll int res[],ll int res_size);

void factorial(ll int n)
{
    ll int res[MAX];

    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);

    cout << "Factorial of given number is \n";
    for (ll int i=res_size-1; i>=0; i--)
        cout << res[i];
}

ll int multiply(ll int x,ll int res[],ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    factorial(100);
    return 0;

}

Prime Factorization of Factorial Source code

Tutorial Link : http://blog.forthright48.com/2015/08/prime-factorization-of-factorial.html

Source Code :

#include<bits/stdc++.h>

using namespace std;

bool status[1100001];

vector<int>prime;

void sieve()
{
    int n=1000001;
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i;j<=n;j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3;i<=n;i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void fact ( int n ) {
    for ( int i = 0; i < prime.size() and prime[i]<= n; i++ ) {
        int x = n;
        int freq = 0;

        while ( x / prime[i] ) {
            freq += x / prime[i];
            x = x / prime[i];
        }

        printf ( "%d^%d ", prime[i], freq );
    }
}
int main()
{
    sieve();

    int n;
    cin>>n;
    fact(n);

}

Segmented Sieve Source Code

#include<bits/stdc++.h>

using namespace std;

bool status[1010000];

vector<int>prime;

void sieve()
{
    int n=1000100;
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i;j<=n;j=j+(2*i)) status[j]=true;
        }
    }
    status[0]=true;
    status[1]=true;

    for(int i=2;i<=n;i++)
    {
        if(status[i]==false) prime.push_back(i);
    }
}

int arr[100010];

int sgmnt_sieve(int a,int b)
{
    memset(arr,0,sizeof(arr));

    if(a==1) a++;

    int sq=sqrt(b);

    for(int i=0;i<prime.size() and prime[i]<=sq;i++)
    {
        int p=prime[i];
       long long  int j=p*p;

        if(j<a) j=((a+p-1)/p)*p;

        for(;j<=b;j=j+p)
        {
            if(j<0) break;
            arr[j-a]=1;
        }

    }
    int cnt=0;

    for(int i=a;i<=b;i++)
    {
        if(arr[i-a]==0) cnt++;
    }

   return cnt;
}

int main()
{
    sieve();

int a,b,t,ca=1;
cin>>t;
    while(t--)
    {
           cin>>a>>b;
    cout<<"Case "<<ca<<": "<<sgmnt_sieve(a,b)<<endl;
ca++;
    }
}

Extended Euclid source code

Tutorial Link : http://blog.forthright48.com/2015/07/extended-euclidean-algorithm.html

Theorem : Let the solutions be X and Y , this algorithm gives the result as |X| + |Y | is the minimal. If there are several X and Y satisfying the minimal criteria, then the result follows the condition X ≤ Y.

Source Code :

#include<bits/stdc++.h>

using namespace std;


int X=-1,Y=-1;

int ext_gcd ( int A, int B){
    int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    int a,b;
    cin>>a>>b;

    int e=ext_gcd(a,b);

    cout<<"Gcd is :"<<e<<" and x="<<X<<" y="<<Y;
}

EulerPhi source code

Theorem 1: If m and n are coprime, then ϕ(m×n)=ϕ(m)×ϕ(n)


Theorem 2: In an arithmetic progression with difference of m, if we take n terms and find their modulo by n, and if n and m are coprimes, then we will get the numbers from 0 to n−1 in some order.

Theorem 3: If a number x is coprime to y, then (x%y) will also be coprime to y.

#include<bits/stdc++.h>

using namespace std;

bool status[11000010];

vector<int>prime;

void sieve()
{
    int n=10000010;
    int sq=sqrt(n);

    for(int i=4; i<=n; i=i+2) status[i]=true;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==false) prime.push_back(i);
    }
}

long long int EulerPhi(long long int n)
{
    long long  int res=n;
    long long int sq=sqrt(n);

    for(long long int i=0; i<prime.size() and prime[i]<=sq; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n=n/prime[i];
            }
            sq=sqrt(n);
            res=res/prime[i];
            res=res*(prime[i]-1);
        }

    }
    if(n!=1)
    {
        res=res/n;
        res=res*(n-1);
    }
    return res;
}

int main()
{
    sieve();
    long long int n;

    while(cin>>n)
    {
        cout<<EulerPhi(n)<<endl;
    }
}

Euler phy function as sieve

#include<bits/stdc++.h>
using namespace std;

#define M 10000050

int phi[M];

int main()
{

  for (int i = 1; i < M; i++) {
    phi[i] = i;
  }
int t,w;
  for (int p = 2; p < M; p++) {
         w=phi[p];
    if (phi[p] == p) { // p is a prime
      for (int k = p; k < M; k += p) {
        phi[k] -= phi[k] / p;
   t=phi[k];

      }
    }
  }

}

Bitwise sieve source code

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100000000;  // 10^8
const int LMT =     10000;  // sqrt(MAX)

int _c[(MAX>>6)+1];

vector<int> primes;

#define IsComp(n)  (_c[n>>6]&(1<<((n>>1)&31)))

#define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))

void prime_sieve() {
    for (int i = 3; i <= LMT; i += 2)
        if (!IsComp(i))
            for (int j = i*i; j <= MAX; j += i+i)
                SetComp(j);

    primes.push_back(2);
    for (int i=3; i <= MAX; i += 2)
        if (!IsComp(i))
            primes.push_back(i);
}

int main()
{

    prime_sieve();
    for(int i=0;i<primes.size();i++) cout<<primes[i]<<endl;
}

Topological Sort Source Code ( 10305 - Ordering Tasks )

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1246

Solve :

#include<bits/stdc++.h>

using namespace std;

vector <int> v[103],top;

int indgre[103];

int main()
{

    int n,e,i,a,b,j,k,l,sp;

    while(cin>>n>>e)
    {
        sp=0;

        if(n==0&&e==0) break;
        memset(indgre,0,sizeof(indgre));
        for(i=1; i<=e; i++)
        {
            cin>>a>>b;
            v[a].push_back(b);
            indgre[b]++;
        }

        for(i=1; i<=n; i++)
        {
            if(indgre[i]==0)
            {
                top.push_back(i);
            }
        }

        for(i=0; i<top.size(); i++)
        {
            k=top[i];

            for(j=0; j<v[k].size(); j++)
            {
                l=v[k][j];
                indgre[l]--;

                if(indgre[l]==0) top.push_back(l);
            }
        }
        for(i=0; i<top.size(); i++)
        {
            if(sp==0) cout<<top[i];
            else cout<<" "<<top[i];
            sp++;
        }
        cout<<endl;
        top.clear();
        for(i=0; i<103; i++)
        {
            v[i].clear();
        }
    }

}

DFS Source Code

#include <bits/stdc++.h>

using namespace std;

vector<int>v[100];
bool visited[100];

int node,edge;

void DFS(int n)
{
    visited[n]=true;
    cout<<n<<" ";
    int temp;
    for(int i=0; i<v[n].size(); i++)
    {
        temp=v[n][i];
        if(!visited[temp])
            DFS(temp);
    }
}


int main()
{
    cin>>node>>edge;
    for(int i=0; i<edge; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int src,dst;
    cin>>src>>dst;
    memset(visited,0,sizeof visited);
    cout<<"DFS traverse order is = ";
    DFS(src);
    cout<<endl;
    if(visited[dst])
        cout<<dst<<" is reachable from "<<src<<endl;
    else
        cout<<dst<<" is not reachable from "<<src<<endl;
    return 0;
}

BFS source code #1

Problem : First you have to store a graph in a adjacency list.Then you have to determine the shortest distance between source and destination node.

Problem link and solution idea : http://www.shafaetsplanet.com/planetcoding/?p=604

Source code :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    cout<<"Eenter node and edge number : ";
    int node,edge;

    cin>>node>>edge;

    vector<int>v[100];

    int i;
    int a,b;
    cout<<"Enter nodes connecting edges : "<<endl;
    for(i=1; i<=edge; i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
    }
    cout<<endl;
    int source,destination;

    while(1)
    {
        cout<<"Source : ";
        cin>>source;
        cout<<"destination : ";
        cin>>destination;

        int visited[100];

        memset(visited,-1,sizeof(visited));

        queue<int>q;

        q.push(source);

        visited[source]=0;

        int u,p;

        while(!q.empty())
        {
            u=q.front();
            q.pop();
            for(i=0; i<v[u].size(); i++)
            {
                p=v[u][i];

                if(visited[p]==-1)
                {
                    visited[p]=visited[u]+1;
                    q.push(p);
                    if(p==destination) break;
                }

            }
        }
        cout<<"Shortest distance betwwen destination and source : ";
        cout<<visited[destination]-visited[source]<<endl<<endl;

    }
    return 0;
}

Array compression with map

problem link : http://www.shafaetsplanet.com/planetcoding/?p=1388

code:

#include<bits/stdc++.h>

using namespace std;

int main()
{
    map<long long int,long long int>mp;

    long long int a[1000];//given array
    long long int b[1000];//compressed/matched array

    long long  int d,c=0,i,j=0;
    long long  int n;
    cin>>n;//array size

    for(i=0; i<n; i++)
    {
        cin>>a[i];//taking array inputs
    }
    cout<<endl;
    for(i=0; i<n; i++)
    {
        d=a[i];
        if(mp.find(d)==mp.end())//checking if map with value d is empty or not
        {
            mp[d]=c;

            cout<<d <<" is matched with "<<c<<endl<<endl;
            c++;
        }
        d=mp[d];
        b[j]=d;
        j++;
    }
    cout<<endl;
    cout<<"compressed/matched array:"<<endl<<endl;
    for(i=0; i<n; i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;
}