Longest Increasing Subsequence with O(N log K)

// LIS -- O(N log K)

#include<bits/stdc++.h>
#define sze 100

using namespace std;

const int inf=9999;

int seq[sze+5], lisseq[sze+5] , n , I[sze+5], L[sze+5];

int Binary_Search(int lo, int hi, int itm)
{
    int mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(I[mid] < itm)
        {
            lo = mid+1;
        }

        else
        {
            hi = mid-1;
        }
    }

    return lo;
}

int LIS()
{
    //memset(L, 1, sizeof(L));

    int i , r , len=0 , llen=0;

    for(i=0; i<n; i++)
    {
        r = Binary_Search(0, len, seq[i]);

        I[r] = seq[i];
        L[llen++] = r;

        if(len < r)
        {
            len = r;
        }
    }

    return len;
}

void find_sequence(int mxlen)
{
    int i=0 , j;

    for(j=1; j<n; j++)
    {
        if(L[i] < L[j])
        {
            i = j;
        }
    }

    int top = L[i];

    top--;

    lisseq[top] = seq[i];

    for(j=i-1; j>=0; j--)
    {
        if(seq[j] < seq[i] and L[j] == L[i] - 1)
        {
            i = j;

            top--;

            lisseq[top] = seq[i];
        }
    }

    cout << "LIS Sequence: ";

    for(i=0; i<mxlen; i++)
    {
        cout << lisseq[i] << " ";
    }
}

int main()
{
    while(cin >> n)
    {
        int ilen=0;

         I[ilen++] = -inf;

        for(int i=0;i<n;i++)
        {
            cin >> seq[i];

            I[ilen++] = seq[i];
        }

        int lislen = LIS();

        find_sequence(lislen);

        cout << "LIS Length: " << lislen << "\n";
    }

    return 0;
}

Find Total Number of Distinct Prime Factors

#include<bits/stdc++.h>

#define limit 100100

using namespace std;

typedef long long LL;
typedef bitset<limit>bs;

int distinctfactors[limit] = {0};

bs bit;

void distinct_Prime_factors()
{
    LL i,j;

    bit.set();
    bit[0] = bit[1] = 0;

    for(i=2; i<limit; i++)
    {
        if(bit[i])
        {
            for(j=i*2; j<limit; j+=i)
            {
                if(!(j % i))
                {
                    distinctfactors[j]+=1;
                }

                bit[j] = 0;
            }
        }
    }
    //for(i=2;i<10;i++)cout<<distinctfactors[i]<<" ";
}

int main()
{
    distinct_Prime_factors();
    cout << "Enter a number to find total distinct prime factor: ";
    int n;
    while(cin >> n)
    {
        cout << "Total Distinct Prime Factor = " << distinctfactors[n] << "\n";

        cout << "Enter a number to find total distinct prime factor: ";
    }

    return 0;
}

Find The Total Number of Prime Factors of a number

#include<bits/stdc++.h>

#define limit 100100

using namespace std;

typedef long long LL;
typedef bitset<limit>bs;

int totalfactors[limit];

bs bit;

void find_total_factors()
{
    LL i,j;
    bit.set();
    bit[0] = bit[1] = 0;

    for(i=2; i<limit; i++)
    {
        if(bit[i])
        {
            totalfactors[i] = 1;

            for(j=i*2; j<limit; j+=i)
            {
                totalfactors[j] = 1 + totalfactors[j / i];

                bit[j] = 0;
            }
        }
    }
}

int main()
{
    find_total_factors();
    cout<<"Enter number to find total factors of that number: ";
    int number;
    while(cin >> number)
    {
        cout<<"Total Factors of " << number << " is = " << totalfactors[number] << "\n";

        cout<<"Enter number to find total factors of that number: ";
    }

    return 0;
}

Big Integer Sum between Two Numbers

#include<bits/stdc++.h>

using namespace std;

void x_y(string a, string b)
{
    int alen=a.size(), blen=b.size(),i,j, sum, carry=0, num[1009], numlen=0;

    i=alen-1;
    j=blen-1;

    for(; i>=0; i--)
    {
        sum = a[i]-48;

        if(j>=0)
        {
            sum+=(b[j]-48);
            j--;
        }

        sum+=carry;

        if(sum > 10)
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }
        else
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }

        numlen++;
    }

//    if(carry)
//    {
//        cout << carry;
//    }

    if(carry)
    {
        num[numlen++]=carry;
    }

    for(i=numlen-1; i>=0; i--)
    {
        cout << num[i];
    }

    cout << endl;
}

void eql(string a, string b)
{
    int alen=a.size(), blen=b.size(), i, j, sum, carry=0, num[1009], numlen=0;

    i=alen-1;
    j=blen-1;

    for(; i>=0 and j>=0; i--,j--)
    {
        sum = (a[i]-48) + (b[j]-48);

        sum+=carry;

        if(sum > 10)
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }

        else
        {
            num[numlen]=sum%10;
            carry=sum/10;
        }

        numlen++;
    }

    if(carry)
    {
        cout << carry;
    }

    for(i=numlen-1; i>=0; i--)
    {
        cout << num[i];
    }

    cout << endl;
}

int main()
{
    string x,y;

    while(cin >> x >> y)
    {
        if(y.size() > x.size())
        {
            swap(x,y);
        }

        if(x.size() > y.size())
        {
            x_y(x,y);
        }

        else
        {
            eql(x,y);
        }
    }

    return 0;
}

sscanf/sprintf (stdio.h/cstdio)

#include<bits/stdc++.h>

using namespace std;

#define pf printf

int main()
{
    //cout << "hello";

    char ch[20];
    gets(ch);

    int cid;
    char name[100];
    int solved;

    sscanf(ch, "%d %s %d", &cid,&name,&solved); // String theke data read korar jonno

    pf("%d %s %d\n",cid,name,solved);

    int n=1001;
    char cr[10];

    sprintf(cr, "%d", n); // kono kichuke Char e convert korte
    pf("%s",cr);

    return 0;
}

Number of Divisors/factors (DP Approach)

for only Prime Factors 

int num[mx7+9];

void nof()
{
    int i,j;

    for(i=4;i<=mx7;i+=2)
    {
        num[i] = 2;
    }

    for(i=3;i*i<=mx7;i+=2)
    {
        if(!num[i])
        {
            for(j=i*i;j<=mx7;j+=i)
            {
                num[j] = i;
            }
        }
    }

    for(i=2;i<=mx7;i++)
    {
        int n = num[i] ? num[i] : i;
        num[i] = 1 + num[i/n];
    }

    for(i=2;i<=21;i++)cp(num[i]);
}

int main()
{
    nof();
} 

Is n a Perfect Square ?

// Header file begin
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<cmath>
#include<cctype>
#include<sstream>
#include<set>
#include<list>
#include<stack>
#include<utility>
#include<queue>
#include<algorithm>
#include<cstdlib>
// End
//..........
// Macro
#define sf scanf
#define pf printf
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define mem(c,v) memset(c,v,sizeof(c))
#define cp(a) cout<<" "<<a<<" "
#define nl puts("")
#define sq(x) ((x)*(x))
#define all(x) x.begin(),x.end()
#define reall(x) x.rbegin(),x.rend()
#define s_wap(x,y) x^=y;y^=x;x^=y;
#define sz size()
#define gc getchar()
#define pb push_back
#define freader freopen("input.txt","r",stdin)
// End.........

// Size
#define mx7 20000100
#define mx6 1500000
#define mx5 100005
#define mx4 1000100
#define inf 1<<30                                           //infinity value
#define eps 1e-9
#define mx (65540)
#define mod 1000000007
#define pi acos(-1.0)

// Macros for Graph

#define white 1
#define gray 2
#define black 3
#define nil 0

using namespace std;
/***************/

// typedef

typedef long long LL;
typedef long L;
typedef unsigned long long ull;
typedef unsigned long ul;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int>vi;
typedef vector<long long> vll;
typedef vector<long>vl;
typedef vector<char>vch;
typedef vector<string>vs;
typedef map<int,int>mpii;
typedef map<int,bool>mpbi;
typedef map<long,bool>mpbl;
typedef map<long long,bool>mpbll;
typedef map<char,int>mpci;
typedef map<char,bool>mpbc;
typedef map<string,int>mpsi;
typedef map<long long,long long>mpll;

// template

template<class T> T gcd(T a, T b ) {return b!=0?gcd<T>(b,a%b):a;}
template<class T> T large(T a, T b ) {return a>b?a:b;}
template<class T> T small(T a, T b ) {return a<b?a:b;}
template<class T> T diffrnce(T a, T b) {return a-b<0?b-a:a-b;}

int prime[(mx>>6)+1],prm[(mx>>1)+9],plen=0,qrt=(int)sqrt(double(mx));

#define setbit(n) (prime[n>>6] |= (1<<((n>>1)&31)))
#define checkbit(n) (prime[n>>6] & (1<<((n>>1)&31)))

void sieve()
{
    int i,j;
    for(i=3;i<=qrt;i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i;j<=mx;j+=i+i)
            {
                setbit(j);
            }
        }
    }
    prm[plen++]=2;
    for(i=3;i<=mx;i+=2)
    {
        if(!checkbit(i))
        {
            prm[plen++]=i;
        }
    }
    //lp1(i,100)cp(prm[i]);
}

mpii mp;

void factors(int n)
{
    mp.clear();
    int i,keep=n;
    bool yes1=false,yes2=false;
    for(i=0;i<plen and sq(prm[i])<=n;i++)
    {
        if(!(n%prm[i]))
        {
            while(!(n%prm[i]))
            {
                mp[prm[i]]++;
                n/=prm[i];
                if(n==0 or n==1)break;
            }

            if(!(mp[prm[i]]&1))
            {
                yes1=true;
            }
        }
    }

    if(n>1)
    {
        mp[n]++;
    }
    if(!(mp[n]&1))
    {
        yes2=true;
    }
    if(yes1)
    {
        if(yes2)
        {
            cout<<"Yes: " << keep << " is a perfect square\n";
        }
        else
        {
            cout<<"No: " << keep << " is not a perfect square\n";;
        }
    }
    else
    {
        cout<<"No: " << keep << " is not a perfect square\n";
    }
}

int main()
{
    sieve();
    int n;
    while(cin >> n)
    {
        if(n==1)
        {
            cout<<"Yes: " << n << " is a perfect square\n";
            continue;
        }

        factors(n);
    }

    return 0;
}