Stack Implementation

Stack Implementation in C++ through an array

#include < iostream >
        using namespace std;
        #define STACKSIZE 10
        class stack
        {
                private:
                        int arr[STACKSIZE+1];
                        int tos;
                public:
                        stack();
                        void push(int x);
                        int  pop();
                        bool is_empty();
                        bool is_full();
                        int  size();
                        void display();
        };

        stack::stack()
        {
                tos = 0;
        }

        void stack::push(int x)
        {
                if(!is_full())
                        arr[tos++] = x;
                else
                        cout << "Stack is full, Can not push " << x << endl;
        }

        int stack::pop()
        {
                if(!is_empty())
                        return arr[--tos];
                else
                        cout << "Stack is empty, cannot pop" << endl;
                return -1;
        }

        bool stack::is_empty()
        {
                if(tos == 0)
                        return true;
                else
                        return false;
        }

        bool stack::is_full()
        {
                if(tos == STACKSIZE)
                        return true;
                else
                        return false;
        }

        int stack::size()
        {
                return tos;
        }

        void stack::display()
        {
                if(tos == 0)
                {
                        cout << "No elements to display" << endl;
                        return;
                }
                for(int i=0;i
                        cout << arr[i] << " ";
                cout << endl;
        }

        int main()
        {
                stack mystack;
                cout << mystack.size() << endl;
                mystack.push(1);
                if(mystack.is_full())
                        cout << "stack is full" << endl;
                mystack.pop();
                if(mystack.is_empty())
                        cout << "stack is empty" << endl;
        }

Bitwise Operations Tutorial

Common Bitwise Operations

x & (x-1) - Returns number x with the lowest bit set off. Also to check if an integer is a power of 2.

x ^ ( x & (x-1 )) - Returns the lowest bit of a number x.

x & 1 < < n - Returns 1 < < n is the n-th bit is set in x.

x | 1 < < n - Returns the number x with the n-th bit set.

x ^ 1 < < n - Toggles the state of the n-th bit in the number x.

Finding GCD and LCM

The best way to find GCD of two numbers is by using Euclid's Algorithm.

 

Which also could be written as

Below is a simple implementation of Euclid's algorithm in C++,

        #include
        using namespace std;

        int gcd(int a, int b)
        {
                if(b==0) return a;
                return gcd(b,a%b);
        }
        int main()
        {
                cout << "GCD of 84 and 18 is " << gcd(84,18) << endl;
        }
Output:
        GCD of 84 and 18 is 6.

GCD and LCM are related by a very simple equation,

This way the problem of computing the least common multiple can be reduced to the problem of computing the greatest common divisor (GCD).

The above code can be modified to include LCM function as,

        #include
        using namespace std;

        int gcd(int a, int b)
        {
                if(b==0) return a;
                return gcd(b,a%b);
        }
        int lcm(int a, int b)
        {
                return a*b/gcd(b,a%b);
        }
        int main()
        {
                cout << "GCD of 84 and 18 is " << gcd(84,18) << endl;
                cout << "LCM of 84 and 18 is " << lcm(84,18) << endl;
        }

Output:
        GCD of 84 and 18 is 6.
        LCM of 84 and 18 is 252.

Prime Numbers

In several puzzles/coding competitions we may need to check for prime numbers and this is required to be done in considerable time to save precious run time. The traditional approach is,

        bool is_prime(int x)
        {
                if(x <= 1)
                return false;

                for(int i = 2; i < x; i++)
                        if(x%i == 0)
                                return false;

                return true;
        }

This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,

        bool is_prime(int x)
        {
                if(x <= 1)
                return false;

                for(int i = 2; i <= x/2; i++)
                        if(x%i == 0)
                                return false;
 
                return true;
        }

But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be

        bool is_prime(int x)
        {
                if(x <= 1)
                        return false;

                int s = (int) sqrt(x);
                for(int i = 2; i <= s; i++)
                        if(x%i == 0)
                                return false;

                return true;
        }

This approach will check for factors in very minimized number of loops.

Dynamic Programming

DP Problem #1: Minimum steps to one
        Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

Example:
        Given coins with values 1, 3, and 5.
        And the sum S is set to be 11.

Solution:

#include

using namespace std;

#define INFINITE 999999

int main()
{
        const int S = 11; // sum to calculate.
        const int N = 3;  // number of coins available.
        int v[N] = {1,3,5}; // face value of all the coins.
        int min[S+1];

        for(int i=0;i<12;i++)
                min[i] = INFINITE; // we havent yet found a solution for this one.

        min[0] = 0; // sum of 0 requires minimum number of 0 coins.

        for(int s=1;s<=S;s++) // start from 1 since we have found a solution for sum = 0.
        {
                for(int n=0;n
                {
                        if(v[n]<=s && min[s]>1+min[s-v[n]])
                        {
                                min[s] = min[s-v[n]]+1;
                        }
                }
        }
        cout << "Coins required for sum[" << S << "] = " << min[S] << endl;
}

Output:
Coins required for sum[11] = 3

DP Problem #2: Maximum number of apples
        A table composed of NxM cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of apples you can collect.

Example:
    Consider the table as described in the code

Solution:
#include

int max(int a, int b)
{
        return (a>b)?a:b;
}

int main()
{
        const int N = 10;
        const int M = 10;
        int A[N+1][M+1] = {     {1,2,3,4,5,6,7,8,9,0},
                                {2,4,6,8,0,1,3,5,7,9},
                                {1,1,1,1,1,1,1,1,1,1},
                                {3,5,7,9,2,4,6,7,4,3},
                                {3,3,3,6,4,6,2,3,4,6},
                                {4,9,1,3,1,8,8,1,5,2},
                                {2,1,0,3,9,2,4,3,6,7},
                                {0,0,6,9,8,9,6,1,0,9},
                                {9,4,4,5,1,5,6,6,6,5},
                                {9,8,4,1,0,1,0,1,4,1}};

        int S[N+1][M+1];

        for(int n=0;n<=N;n++)
        {
                for(int m=0;m<=M;m++)
                {
                        S[n][m] = 0;
                        S[n][m] = A[n][m] + max(((m>0)?S[n][m-1]:0),((n>0)?S[n-1][m]:0));
                }
        }

        cout << "Maximum apples collected = " << S[N][M] << endl;
}

Output:
Maximum apples collected = 99 

The path  traversed is 1 - 2 - 4 - 6 - 8 - 1 - 9 - 6 - 3 - 3 - 9 - 8 - 9 - 6 - 6 - 6 - 6 - 5 - 1.

DP Problem #3: Minimum number of coins
    Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.


Example:
    Given coins with values 1, 3, and 5. Find the minimum number of coins for sum 11.


Solution:
#include

using namespace std;

#define INFINITE 999999

int main()
{
        const int S = 11; // sum to calculate.
        const int N = 3;  // number of coins available.
        int v[N] = {1,3,5}; // face value of all the coins.
        int min[S+1];

        for(int i=0;i<12;i++)
                min[i] = INFINITE; // we havent yet found a solution for this one.

        min[0] = 0; // sum of 0 requires minimum number of 0 coins.

        for(int s=1;s<=S;s++) // start from 1 since we have found a solution for sum = 0.
        {
                for(int n=0;n
                {
                        if(v[n]<=s && min[s]>1+min[s-v[n]])
                        {
                                min[s] = min[s-v[n]]+1;
                        }
                }
        }
        cout << "Coins required for sum[" << S << "] = " << min[S] << endl;
}


Output:
Coins required for sum[11] = 3

DP Problem #4: Longest Increasing subsequence
    The Longest Increasing Subsequence problem is to find the longest increasing subsequence of a given sequence. Given a sequence S= {a1 , a2 , a3, a4, ............., an-1, an } we have to find a longest subset such that for all j and i,  ,  j < i in the subset aj < ai.


Example:
    Given sequence 3,5,2,7,1,5,3,8,0,9 find the longest increasing subsequence.
 
Solution:
#include

int main()
{
        const int N = 10;
        int A[N] = {3,5,2,7,1,5,3,8,0,9};
        int LS[N];

        for(int i=0;i
        {
                LS[i] = 1;
                for(int j=0;j
                {
                        if(A[j]<=LS[j])
                                LS[i] = LS[j]+1;
                }
        }
        int l = 0;
        for(int i=0;i
        {
                l = LS[i]>l?LS[i]:l;
        }
        cout << "Longest increasing subsequence :: " << l << endl;
}
 
Output:
Longest increasing subsequence :: 5


DP Problem #5: Longest common subsequence
    Given a sequence of elements, a subsequence of it can be obtained by removing zero or more elements from the sequence, preserving the relative order of the elements. Note that for a substring, the elements need to be contiguous in a given string, for a subsequence it need not be. Eg: S1="ABCDEFG" is the given string. "ACEG", "CDF" are subsequences, where as "AEC" is not.


Example:
    Given strings "XMJYAUZSS" and "MZJAWXU", find the longest common subsequence.


Solution:
#include

#define MAX 100

unsigned int C[MAX][MAX];

int lcs_length(char *X, char *Y)
{
        size_t M = strlen(X), N = strlen(Y);

        for(int i=0;i<=(int)M;i++)
                C[i][0] = 0;
        for(int j=0;j<=(int)N;j++)
                C[0][j] = 0;

        for(int i=1;i<=(int)M;i++)
        {
                for(int j=1;j<=(int)N;j++)
                {
                        if(X[i] == Y[j])
                                C[i][j] = C[i-1][j-1] + 1;
                        else
                                C[i][j] = C[i][j-1]>C[i-1][j]?C[i][j-1]:C[i-1][j];
                }
        }
        return C[M][N];
}

int main()
{
        char *X = "XMJYAUZSS", *Y = "MZJAWXU";

        cout << "Longest common subsequence :: " << lcs_length(X,Y) << endl;
}


Output:
Longest common subsequence :: 4