Subset sum problem.

Problem Statement: Given a set of numbers A[1...n], find a subset which sums up to a given number S.

Solution #1: Below is the code using Brute-force approach. The complexity is O(2^n).

int subsetSum(int* A, int len, int sum)
{
    if(sum == 0)
        return 1;
    
    if((len < 0) || (sum < 0))
        return 0;

    return subsetSum(A+1, len-1, sum) || subsetSum(A+1, len-1, sum-A[0]);
}

Solution #2: A faster way to solve this problem is by using dynamic programming. Below is the equation and the code,

RES[i][j] : is '1' if there is a subset in set A[1...i] which sums up to 'j', '0' otherwise.

RES[i][j] = RES[i-1][j] | RES[i-1][j-A[i]]

int RES[100][100];

int subsetSumDyn(int* A, int len, int sum)
{
    int i,j;

    for(j=0; j<=sum; j++)
        RES[0][j] = 0;
    
    for(i=0; i<=len; i++)
        RES[i][0] = 1;

    for(i=1; i<=len; i++)
    {
        for(j=1; j<=sum; j++)
        {
            int index = j - A[i-1];
            if(index >=0)
                RES[i][j] = RES[i-1][j] | RES[i-1][index];
            else
                RES[i][j] = RES[i-1][j];
        }
    }

    return RES[len][sum];
}

int main()
{
    int A[] = {13, 21, 11, 14, 4, 5};
    int len = sizeof(A)/sizeof(int);

    printf("Subset sub: %d\n", subsetSumDyn(A, len, 32));
    return 0;
}

Maze Algorithm.

Problem Statement: A mouse is at one corner of a maze and he has to reach the corner diagonally opposite to him. Write an algorithm to find the path through the maze. The maze is represented by a matrix of '0's and '1's where '1' denotes a path and '0' denotes a wall.

This problem can be solved using backtracking. Below is the code,

#define N 4

void printMaze(int maze[N][N])
{
    int i, j;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N; j++)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
}

void move(int maze[N][N], int sol[N][N], int x, int y)
{
    if((x == N-1) && (y == N-1))
    {
        sol[x][y] = 1;
        printMaze(sol);
        return;
    }

    if(x != N-1)
    {
        if(maze[x+1][y])
        {
            sol[x][y] = 1;
            move(maze, sol, x+1, y);
            sol[x][y] = 0;
        }
    }

    if(y != N-1)
    {
        if(maze[x][y+1])
        {
            sol[x][y] = 1;
            move(maze, sol, x, y+1);
            sol[x][y] = 0;
        }
    }
}

int main()
{
    int maze[N][N] = 
    {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0,};

    move(maze, sol, 0, 0);
    return 0;
}

Edit Distance.

Problem Statement: The edit distance between two words is the minimum number of letter insertions, letter deletions and letter substitutions required to transform one word into another. For e.g. edit distance between "food"and "money" is 4. Below is the equation and the code for the problem,

min[i, j] = MIN(min[i-1, j] + 1, min[i, j-1] + 1, min[i-1, j-1] + (A[i] != B[j]))

#define MIN(a, b) ((a)<(b))?(a):(b)

int min[100][100];

int editDistance(char* A, char* B)
{
    int n = strlen(A);
    int m = strlen(B);

    int i, j;

    for(i=0; i <= n; i++)
        min[i][0] = i;
    
    for(j=0; j <= m; j++)
        min[0][j] = j;

    for(i=1; i <= n; i++)
    {
        for(j=1; j <= m; j++)
        {
            min[i][j] = MIN(min[i-1][j] + 1, min[i][j-1] + 1);
            min[i][j] = MIN(min[i][j], min[i-1][j-1] + (A[i-1]!=B[j-1]));
        }
    }

    return min[n][m];
}

int main()
{
    char A[50] = {0, };
    char B[50] = {0, };

    sprintf(A, "%s", "food");
    sprintf(B, "%s", "money");

    printf("EDIT DISTANCE: %d\n", editDistance(A, B));
    return 0;
}

Given two strings, print all interleaving strings.

Solution #1: Note that interleaving of two strings does not change the actual order of the characters within the two strings. For e.g.

str1 = "AB"
str2 = "MN"

So, in the output string, 'A' will always come before 'B' and 'M' will always come before 'N' .

Interleaving strings are,

ABMN
AMBN
AMNB
MABN
MANB
MNAB

void interleave(char* str1, char* str2, char* str, int len)
{
    int i=0;

    //if both input strings reach null, print final string and return
    if(str1[0] == '\0' && str2[0] == '\0')
    {
        printf("%s\n", str-len);
        return;
    }

    if(str1[0] != '\0')
    {
        str[0] = str1[0];
        interleave(str1+1, str2, str+1, len);
    }
    if(str2[0] != '\0')
    {
        str[0] = str2[0];
        interleave(str1, str2+1, str+1, len);
    }
}

int main()
{
    char* str1 = "AB";
    char* str2 = "MNO";

    //get length of input strings
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int len = len1+len2;

    //allocate memory for output string
    char* str = (char*)malloc(len+1);
    memset(str, 0, len+1);

    interleave(str1, str2, str, len);
    return 0;
}

Longest Increasing Subsequence problem.

Problem Statement: Given an array of integers, determine the longest increasing subsequence (not necesarily contiguous).

Solution #1: Below is the equation and the code for the problem,

Equations:
LIS[i] = MAX( LIS[j] ) + 1; where 0 <= j < i and A[i] > A[j]

#define MAX(a, b) ((a)>(b))?(a):(b)

int LIS[1000];

int lis(int* A, int len)
{
    int i, j;
    int max;

    LIS[0] = 1;

    for(i=1; i < len; i++)
    {
        max = 0;
        for(j=0; j < i; j++)
        {
            if(A[i] > A[j])
                max = MAX(max, LIS[j]);
        }

        printf("max: %d\n", max);

        LIS[i] = max + 1;
    }

    return LIS[len-1];
}

int main()
{
    int A[] = {4, 3, 9, 4 ,1 ,6};

    printf("LIS: %d\n", lis(A, 6));
    return 0;
}

Longest common subsequence problem.

Problem Statement: Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Solution #1: A Brute force approach will take exponential time to solve this problem. We will use dynamic programming to solve it in O(mn) time and space. Below is the equation and the code for the problem,


LCS[i, j] = LCS[i-1][j-1] + 1 ; arr1[i] == arr2[j]
               = MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise

#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}

Count bits in an integer.

Solution #1: The most straightforward approach is to check each bit one by one. Here is the code,

int count1(int n)
{
    int count=0;

    while(n)
    {
        if(n&1)
            count++;

        n = n>>1;
    }

    return count;
}

Solution #2: The below code is an efficient version which improves the average time,

int count2(int n)
{
    int count=0;

    while(n)
    {
        count++;
        n = n&(n-1);
    }

    return count;
}

Coin denomination problem

Problem Statement: You are given n types of coin denominations of values d1 < d2 < ... < dn (all integers). Give an algorithm which makes change for an amount of money C with as few coins as possible.

Solution #1: Let min[i] represents the minimum number of coins required to make the change 'i'. Now, minimum number of coins required to make change 'C' = min[C-dj] + 1, where d1 <= dj <= dn. Below is the code with comments,

#define INFINITY 99999

int min[1000] = {0, };


int coins(int* arr, int len, int c)
{
    int i,j;

    //initialize all elements with INFINITY i.e.
    //infinite coins needed to make ith change
    for(i=0; i<=c; i++)
        min[i] = INFINITY;

    //0 coins are needed to get 0 change!
    min[0] = 0;

    //1 coin is needed to get the change equal to
    //any of the available coins
    for(i=0; i < len; i++)
        min[arr[i]] = 1;

    for(i=0; i<=c; i++)
    {
        for(j=0; j < len; j++)
        {
            int index = i-arr[j];
            if(index < 0)
                continue;

            if(min[index]+1 < min[i])
                min[i] = min[index]+1;
        }
    }

    return min[c];
}

int main()
{
    int arr[] = {4, 5, 7};
    printf("COINS: %d\n", coins(arr, 3, 166));

    return 0;
}