Bubble Sort

void bubble_sort ( vector < int > a ) {

        int n = a.size();

        for (int i = 1; i < n - 1; i++) {

                for (int j = 0; j < n - i; j++) {

                        if (a[j] > a[j+1]) {

                                int temp = a[j];

                                a[j] = a[j+1];

                                a[j+1] = temp;

                        }

                }       

        }

}

Selection sort

void selection_sort ( vector < int > a ) {

    int min_index = -1;

    for (int i = 0; i < n - 1; i++) {

        min = i;

        for (int j = i+1; j< n; j++) {

            if (a[j] < min_index) {

                min_index =  j;

            }

        }

        int temp = a[i];

        a[i] = a[min_index];

        a[min_index] = temp;

    }

}

Insertion Sort

void insertion_sort ( vector <int> arr ) {

    int key = 0;

    int j = 0;

  

    for (int i = 1; i < arr.size(); i++) {

        key = arr[i];

        j = i - 1;

        while(j > = 0 && arr[j] > key) {

            arr[j+1] = arr[j];

        }

        arr[j+1] = key;

    }

}

Longest common subsequence

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

void lcsutil (vector <int> & first, vector <int> & second, vector <vector <int> > & arr) {

    int m = first.size();

    int n = second.size();

    

    for (int i = 0; i <= n; i++) {

        arr[0][i] = 0;

    }

    

    for (int i = 0; i <= m; i++){

        arr[i][0] = 0;

    }

    

    for (int i = 1; i <= m; i++) {

        for (int j = 1; j <= n; j++) {

            if (first[i-1] == second[j-1]) {

                arr[i][j] = arr[i-1][j-1] + 1;

            } else if (arr[i-1][j] >= arr[i][j-1]) {

                arr[i][j] = arr[i-1][j];

            } else if (arr[i][j-1] > arr[i-1][j]){

                arr[i][j] = arr[i][j-1];

            }

        }

    }

    

    int index = arr[m][n];

    vector <int> longest (index);

    index--;

    

    int i = m;

    int j = n;

    

    while (i > 0 & j > 0) {

        if (first[i-1] == second[j-1]) {

            longest[index] = first[i-1];

            index--;

            i--;

            j--;

        } else if (arr[i-1][j] > arr[i][j-1]) {

            i--;

        } else {

            j--;

        }

    }

    

    for (int i = 0; i < arr[m][n]; i++){

        cout<<longest[i]<<" ";

    }

}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    unsigned int m, n;

    

    cin>>m>>n;

    

    vector < int > first(m);

    vector < int > second(n);

    

    for (int i = 0; i < m; i++) {

        cin>>first[i];

    }

    

    for (int i = 0; i < n; i++) {

        cin>>second[i];

    }

    

    vector < vector <int> > arr ( m + 1 , vector <int> (n + 1));

    

    lcsutil (first, second, arr);

    

    return 0;

}

Djkstra Algorithm

Djsktra algorithm is used to find shortest path between two vertices in a graph

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

#include <climits>

using namespace std;

long long getMinimumIndex (long long start, vector < vector < long long > > &a, vector < long long >  & dis, vector < long long > &spf) {

    

    long long min_index = 1;

    

    for (long long i = 1; i < dis.size(); i++) {

        if (!spf[i]) {

            min_index = i;

            break;

        }

    }

    

    long long min_value = dis[min_index];

    

    for (long long i = 1; i < dis.size(); i++){

        

        if (min_value > dis[i] && !spf[i]) {

            min_value = dis[i];

            min_index = i;

        }

    }

    

    return min_index;

}

void djkstra (vector <vector <long long> > &a, const long long & start, const long long & nodes) {

    

    vector <long long> dis (nodes + 1);

    vector <long long> spf (nodes + 1);

    long long min_index = 0;

    std::fill (dis.begin(), dis.end(), LLONG_MAX);

    std::fill (spf.begin(), spf.end(), 0);

    

    dis[start] = 0;

    

    for (int i = 1; i <= nodes; i++) {

        

        min_index = getMinimumIndex (i, a, dis, spf);

        

        cout<<"\n The selected index is "<<min_index;

        

        spf[min_index] = 1;

        

        for (int j = 1; j <= nodes; j++) {

            if (a[min_index][j]) {

                if (dis[j] > dis[min_index] + a[min_index][j]) {

                    dis[j] = dis[min_index] + a[min_index][j];

                }

            }

        }

        

        /*for (long long i = 1; i <= nodes; i++) {

             if (i != start) {

                 cout<<dis[i]<<" ";

             }

        }*/

    }

    

    for (long long i = 1; i <= nodes; i++){

        if (i != start) {

            if (dis[i] != LLONG_MAX){

                cout<<dis[i]<<" ";

            } else {

                cout<<"-1"<<" ";

            }

        }

    }

}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    

    int t;

    cin>>t;

    

    while (t--) {

        

        long long nodes;

        long long edges;

        long long start  = 0;

        

        cin>>nodes>>edges;

        

        vector < vector <long long> > a (nodes + 1, vector < long long > (nodes + 1));

        

        for (long long i = 1; i <= nodes; i++) {

            

            std::fill(a[i].begin(), a[i].end(), 0);

        }

        

        for (long long i = 1; i <= edges; i++) {

            

            long long from, to, dis;

            

            cin>>from>>to>>dis;

            

            if (!a[from][to] || a[from][to] > dis) {

                a[from][to] = dis;

                a[to][from] = dis;

            }

        }

        

        cin>>start;

        

        djkstra (a, start, nodes);

        

        cout<<"\n";

    }

    

    return 0;

}

Combinations of a string

#include <iostream>
using namespace std;

void printCombinations (string s, char * a, int i, int n, int k) {

if (i == k) {
for (int p = 0; p <k; p++) {
cout<<a[p];
}
cout<<"\n";
return;
}

for (int j = 0; j < n; j++) {
a[i] = s[j];
printCombinations (s, a, i+1, n, k);
}
}

void findCombinations(string s, int n, int k) {
char temp[k];
printCombinations (s, temp, 0, n ,k);
}

int main() {

string s;
getline(cin, s);
findCombinations (s, s.length(), 4);
return 0;
}

DP: Given a value C we need to make amount of money C using unlimited supply of coins denominations of values V1,V2,V3,........Vn

Here we have an unlimited supply of coins of some given denominations,say

Coins[] = {V1,V2,V3,........Vn}

We have a amount C
We need to make a sum C using minimum number of coins possible.

This problem is similar to the Integer knapsack problem where we need to fill a knapsack of space S.
We need to optimally fill a knapsack of space S.

Here we need to optimally find the number of coins for an amount of money C using denominations V1,V2, -----, VN

Let M[j]  be the minimum number of coins required to make an amount of j

Then we can say

M[j] = min {M[j - Vi} + 1
            over all i

We can have the solution utilizing the recursive formula

int getMinCoins(int coins_val[], int total_coins, int value) {

    int minCoins[] = new int[value + 1];

    int coins = 65536;

    minCoins[0] = 0;

    for(int i = 1;i<=value;i++) {

        coins = 65536;

        for (int j=0;j<total_coins;j++){

            if (coins_val[j] <= i){

                coins = min(coins, minCoins[i-coins_val[j]]);

            }

        }

        

         if(coins< 65536) {

             minCoins[i] = coins + 1;

         } else {

             minCoins[i] = 65536;

         }

    }

    coins = minCoins[value];

    return coins;

}

Maximum Value Contiguous Subsequence

The goal is to find the maximum value contiguous subsequence in the given array in the most optimum way.

The problem becomes interesting only if the given array contains negative values else the result is sum of the entire array.

To solve the problem consider the following array

A[1.............i............j.............n]

To have the maximum sum for each location we can have

Sum[j] = { max( S[j-1] + A[j], A[j] ) }

Since for each element j we can have only two scenarios either to add it the current window or add a new window.

Code

int maxIncreasingSubsequence (int *a, int len) {
   
    int *s =new int [len];
    s[0] = a[0];
    for (int i = 1;i<len; i++) {
        s[i] = 0;
        s[i] = max (s[i-1] + a[i], a[i]);
    }
   
    return s[i-1];
}

Finding binomial coefficient

Today we will learn how to find the binomial coefficient of a number

since we know

Hence we will make use of this and will find the solution recursively

#include <iostream>

#include <vector>

using namespace std;

unsigned int bin (int n, int k, vector<vector<int> > table)

{

cout<<"\n n="<<n<<"\t k="<<k;

if (n==0)

return 0;

if (!table[n-1][k-1])

table[n-1][k-1] = bin (n-1, k-1, table);

if (!table[n-1][k])

table[n-1][k] = bin (n-1, k, table);

return table[n-1][k-1] + table[n-1][k];

}

int main() {

int n, k;

cin>>n>>k;

std::vector <std::vector<int> > table (

n+1,

std::vector<int> (k+1));

for (int i=0;i<=n ;i++)

table[i][0] = 1;

cout<<bin (n,k, table);

return 0;}

Checking whether a sum exists in array by adding two numbers

Given an array we need to find whether any two numbers in the array add up to the number given

Say the array is

{23,45,34,12,78} and number given is 57.This is possible as 45+12 add up to give 57.

Simple solutions is to use brute force technique.We will see how to solve this is lesser time complexity.

//Given an array and a sum N
int isSumExists (vector<int>a, int N)
{

     int i = 0, j = a.size() - 1;

     //sort the array
     sort (a.begin(), a.end());

     for (int i=0; i<a.size(); i++) {

            //if sum present return 1
            if (a[i] + a[j]   == N)    return 1;
            else if (a[i] + a[j] < N) i++;
            else  j--;
     }

      //control will reach here if sum is not found
      return 0;
}

Numbers ending in 3 have at least one multiple having all ones. for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such a no. , find the smallest such multiple of that number

A straight approach would be to check 11, 111, 1111 and so on to be divisible by that number.But that will not be optimal.

Let's say we have a series M(n) which is 11, 111, 1111 and so on.

So M(1) = 11, M(2) = 111 , etc

and lets assume the number we need to check the divisibility is n.

If M(i) mod n = 0, then you're done (M(i) is the answer), so let's assume it's not.

You want to find M(i+1) mod n.

Since M(i+1) = 10 * M(i) + 1, you can easily calculate

M(i+1) mod n =  (10 * (M(i) mod n) + 1) mod n

Hence the code

int count=1, rem=1;
while(rem)
{

rem= (rem*10+1)%n;

count++;
}

while(count--)
{
cout<<"1";
}