UVA Problem 10405 – Longest Common Subsequence Solution

UVA Problem 10405 – Longest Common Subsequence Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This one is a fun problem. For this problem we need to find Longest Common Sub Sequence length of two given strings. We can solve this using LCS Algorithm discussed in Introduction to Algorithms book. This algorithm is explained in Wikipedia and other programming language implementations can be found here.

I have provided two dynamic programming implementations below with one top down memoized ( *Slower ) and a bottom up ( *Faster ) solution.

Take the string inputs carefully there may be empty lines in between.

Overview:

Simple explanation for solution technique is we apply Dynamic Programming techniques. There are overlapping sub problems that we can combine to get original solutions.

Starting from the end of both strings. If both of the characters in string are same then we can reduce both string size by 1 length. So now if do the reverse meaning add 1 we get original solution.

In case both characters are not same keeping one string same we reduce the other one by 1 length and try to match the last characters again.

This way if two characters are  same we increase LCS length count. Among the sub problem we choose the one with longest length.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

bcacbcabbaccbab
bccabccbbabacbc

a1b2c3d4e
zz1yy2xx3ww4vv

abcdgh
aedfhr

abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0

abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

 


Output:

11
4
3
26
14

Bottom Up Memoized Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10405 Longest Common Subsequence ( LCS )
 * Method:  Memorized Recursive / Top Down Solution
 */

#include<stdio.h>;
#include<string.h>;
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

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

/*
 * If the value is not -1 then it means the value of that sub problem is
 * already calculated. Just return that calculated value
 * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
 * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
 */
int LCS(int i, int j){
    if(lcs[i][j] != -1)
        return lcs[i][j];

    if(x[i-1] == y[j-1])
        lcs[i][j] = LCS(i-1, j-1) + 1;
    else
        lcs[i][j] = maxval( LCS(i-1, j), LCS(i, j-1) );

    return lcs[i][j];
}

int main(){
    register unsigned i, j;
	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * Set -1 to all positions to indicate there are no calculated value
         */
        for(i = 1; i <= xlen; ++i)
            for(j = 1; j <= ylen; ++j)
                lcs[i][j] = -1;

        printf("%d\n", LCS(xlen,ylen) );

	}
	return 0;
}

Top Down DP Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10405 Longest Common Subsequence ( LCS )
 * Method:  Top Down Dynamic Programming Solution
 */

#include<stdio.h>
#include<string.h>
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

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

int main(){
    register int i, j;

	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
         * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
         */
        for(i = 1; i <= xlen; ++i){
            for(j = 1; j <= ylen; ++j){
                if(x[i-1] == y[j-1])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = maxval(lcs[i-1][j], lcs[i][j-1]);
            }
        }

        /*
         * The max length is at the bottom right corner of the table
         */
        printf("%d\n", lcs[xlen][ylen] );

	}
	return 0;
}

UVA Problem 299 – Train Swapping Solution

UVA Problem 299 – Train Swapping Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The problem specifically asks to “find the least number of swaps of two adjacent carriages necessary to order the train”. That’s it.

It is a sorting problem and we have to count the number of swap between adjacent carriages. So a stable must be applied. Here I have provided three codes with insertion sort, bubble sort, merge sort.

Even though merge sort is O(n lg n) because input size is so small ( 0 <= L <= 50 ) it doesn’t make much difference. For Bubble sort though no need to perform swaps 🙂 just count it. A hybrid between insertion and merge sort me be a slight performance booster. I will try to include it later.

The problem UVA 11462 age sort is solved also with merge sort among other sort algorithms. A commented version merge sort can be found there.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

3
3
1 3 2
4
4 3 2 1
2
2 1

Output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Code ( Bubble Sort No Swap ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Bubble Sort No Swap)
 */

#include<stdio.h>

/**
 * c is swap count
 */
static int A[64], c;

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

    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Bubble Sort
         */
        for(i = 0; i < m - 1; ++i){
            for(j = i + 1; j < m; ++j){
                /**
                 * No need to swap elements
                 * This code may be moved input loop
                 */
                if(A[i] > A[j])
                    ++c;
            }
        }

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Code ( Insertion Sort ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Insertion Sort)
 */

#include<stdio.h>

static int A[64], c;

int main(){
    register int n, i, j;
    int m, key;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Insertion sort using inner for loop
         */
        for(i = 1; i < m; ++i){
            key = A[i];
            for(j = i - 1; j >= 0 && A[j] > key; --j){
                A[j + 1] = A[j];
                ++c;
            }
            A[j + 1] = key;
        }

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Code ( Merge Sort Swap Count ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Merge Sort)
 */

#include<stdio.h>
#include<limits.h>

static int A[64], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    int n, i, j, m;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * To understand Merge sort see my UVA solution age sort 11462
         */
        Mergesort(0, m - 1);

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Lower Bound of Fibonacci Big Omega Time Complexity

Lower Bound of Fibonacci Big Omega Time Complexity:


 Code for Recursive Fibonacci Algorithm:

int fib(int n){
	if (n < 2)
		return n;
	else
		return fib(n - 1) + fib(n - 2);
}

Time Complexity Lower Bound ( Big Omega ):

Detailed explanation for calculating the upper and lower bound can be found here.

T(n) =  T(n-1) + T(n-2) + c
	 =  T(n-2) + T(n-3) + c + T(n-2) + c
	 =  2T(n-2) + T(n-3) + 2c
	 >= 2T(n-2) + 2c
	 =  2T(n-3) + T(n-4) + c) + 2c
	 =  2T(n-3) + 2T(n-4) + 2c + 2c
	 =  2T(n-3) + 2T(n-4) + 4c
	 =  2T(n-4) + 2T(n-5) + 2c + 2T(n-4) + 4c
	 =  4T(n-4) + 2T(n-5) + 6c
	 >= 4T(n-4) + 6c
	 =  4T(n-5) + 4T(n-6) + 10c
	 =  4T(n-6) + 4T(n-7) + 4c + 4T(n-6) + 10c
	 =  8T(n-6) + 4T(n-7) + 14c
	 >= 8T(n-6) + 14c
	 =  .......................
	 =  .......................
	 =  2^k T(n - 2k) + (2^(k+1)-2)c



for, k steps, n - 2k = 0 or, 1 the recursion stops
			  => n = 2k
			  => k = n / 2



	so, from the recurrence relation
	= 2^(n/2) * T(0) + (2^((n/2) +1) -2) * c
	= 2^(n/2) * c + (2^((n/2) +1) -2) * c
	= Ω(2^(n/2))

So, the lower bound of for this recursive Fibonacci algorithm implementation is Big Omega of 2n / 2.

Lower Bound:  Ω ( 2n / 2  )

UVA Problem 11462 – Age Sort Solution

UVA Problem 11462 – Age Sort Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

First of all a warning. This is going to be a very very very long post. For this problem i will use various divide and conquer algorithms ( Ex: quick sort, merge sort etc ) & techniques to solve.

The best Solution here takes 0.502 s ( 502 ms ) . If you are looking for a very fast solution this is not the right place. But these code can be optimized to create a very fast solution.  Also sorts such as bubble sort, selection sort, insertion sort, replacement sort won’t be able to sort in time. So you’ll get TLE if you use these sort.

Lets begin:

This is a sorting problem. The only trouble here is the huge count of test cases. But there’s very important line most miss including me. That is ” no individual in that country lives for 100 or more years “. So we may have many many test cases but no input age is more than 100. 🙂

Now lets look at our solution menu,

1. Counting sort ( Just count occurrence of each values, then print them 0 to 100 for ascending order).

2. Binary Merge sort ( 2 partition ).

3. Ternary Merge sort ( 3 partition ).

4. Quick sort ( 2 partition ).

5. Quick sort ( 3 partition ).


The first solution code here ( counting sort ) runs the fastest since it just count elements at each index and prints them. This solution may be made faster by using combination of fread, fwrite, strtok, atoi, stringstream ( <sstream> ) . Although i haven’t used them. If i get time I will try to implement them in future.

I used the other sorts here just demonstrate implementation of merge sort and quick sort algorithms. I may include more sorting algorithms for this problem in future. All codes are well commented take a look below and try to understand their logic.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

5
3 4 2 1 5
5
2 3 2 3 1
0

Output:

1 2 3 4 5
1 2 2 3 3

Counting Sort Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Counting Sort
 */

#include<stdio.h>
#include<string.h>

static unsigned A[128];

int main(){
    register unsigned n, i, c;
    unsigned num;
    while(scanf("%u", &n) && n){             /* Test cases */
        memset(A, 0, sizeof A);              /* Clear memory for each test case */
        for(i = n; i; --i){                  /* Exits Loop when i is 0 */
            scanf("%u", &num);
            ++A[num];                        /* Since input is never greater than 100, we can use that as index and count occurrence of that index */
        }
        c = i = 1;                           /* i starts from 1 since i is never 0  */
        for(; i<100; ++i){
            while(A[i]--){                   /* Decrease number count at that index */
                if(c == n) printf("%u", i);  /* For the last item in sorted output there is no space */
                else{
                    printf("%u ", i);        /* Just print the index since that was our original input */
                    ++c;                     /* Counter to check if the last element is reached */
                }
            }
        }
        printf("\n");                        /* Print a new line for each test case */
    }
    return 0;
}

 Counting Sort Code ( Usage of stringstream, *slower ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Description: stringstream demo
 */

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>

using namespace std;

static unsigned A[128];

int main(){
    register unsigned n, c, i;
    unsigned num;
    string B;
    while(1){
        scanf("%u", &n); getchar();
        if(!n) return 0;

        memset(A, 0, sizeof A);
        getline(cin, B);

        stringstream ss;
        ss << B;
        while(ss >> num)
            ++A[num];


        c = i = 1;
        for(; i < 100; ++i){
            while(A[i]--){
                if(c == n) printf("%u", i);
                else{
                    printf("%u ", i);
                    ++c;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

 Binary Merge Sort Code ( 2 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Binary Merge Sort ( 2 Partition )
 */

#include<stdio.h>
#include<limits.h>

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid, register unsigned rear){
    register unsigned n1 = mid-front+1;         /* Calculate size of left half of the array */
    register unsigned n2 = rear - mid;          /* Calculate size of right half of the array */

    unsigned *L = new unsigned[n1 + 1];     /* Dynamically create and allocate calculated amount of memory */
    unsigned *R = new unsigned[n2 + 1];     /* plus 1 to hold Infinity or A Very large value for which any input can't be larger than */

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front+i];                          /* Copy elements from given original array to left sub array */

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];                          /* Copy elements from given original array to right sub array */


    L[n1] = INT_MAX;                                /* In the last position of sub array set a very large value */
    R[n2] = INT_MAX;
    i = j = 0;

    register unsigned k = front;                /* Instead of wasting space creating a new array, we can use the original large array since we have already copied all items to sub arrays */
    for(; k <= rear; ++k){
        if(L[i] <= R[j])
            A[k] = L[i++];             /* Compare and copy smaller elements of sub arrays onto original array */
        else
            A[k] = R[j++];
    }
}

void Mergesort(register unsigned front, register unsigned rear){
    if(front < rear){
       register unsigned mid = (rear+front) >> 1;  /* Find the mid point of the array */
                                                    /* Shift bits to right once, equivalent of divided by TWO */

       Mergesort(front, mid);                       /* Recursively divide array in left portion */
       Mergesort(mid+1, rear);                      /* Recursively divide array in right portion */

       Merge(front, mid, rear);                     /* Merge the divided array back again in sorted order */
    }
}

int main(){
    register unsigned n, i;
    while(scanf("%u", &n) && n){
        for(i=0; i<n; ++i)
            scanf("%u", &A[i]);

        Mergesort(0, n-1);                          /* Call merge sort function for each test case */

        for(i = 0; i<n; ++i){
            printf("%u", A[i]);
            if(i != n - 1)
                printf(" ");                 /* Do not print a space after last sorted item */
        }
        printf("\n");
    }
    return 0;
}

 Ternary Merge Sort Code ( 3 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Ternary Merge Sort ( 3 Partition )
 */

#include<stdio.h>
#include<limits.h>

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid1, register unsigned mid2, register unsigned rear){
    /*
     * Calculate size for creating sub array
     * In this case calculate size for three sub arrays
     */
    unsigned n1 = mid1 - front + 1;
    unsigned n2 = mid2 - mid1;
    unsigned n3 = rear - mid2;

    /*
     * Dynamically allocate memory for three sub arrays
     * Here Plus One because we will set a very large value for last position of the array
     */
    unsigned *L = new unsigned[n1 + 1];
    unsigned *R = new unsigned[n2 + 1];
    unsigned *X = new unsigned[n3 + 1];

    /*
     * Copy 1/3 of original array to sub arrays
     * First 1/3 to L array, next 1/3 to R array, last 1/3 to X array
     */
    register  int i = 0;
    for(; i<n1; ++i)
        L[i] = A[front + i];

    for(i=0; i<n2; ++i)
        R[i] = A[mid1 + 1 + i];

    for(i = 0; i < n3; ++i)
        X[i] = A[mid2 + 1 + i];

    /*
     * INT_MAX is found in <limits.h>
     * Instead of traversing the whole array increasing runtime
     * We can compare every element again a very large value which will always be grater than or equal to any input
     */
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    X[n3] = INT_MAX;

    /*
     * Reset index counter for sorting
     */
    i = 0;
    register unsigned p = 0, j = 0, k = front;

    /*
     * Sort:
     * Compare items of each array against each other
     * Copy back the smaller item from the comparison to original array
     */
    for(; k <= rear; ++k){
        if(L[i] <= R[j] && L[i] <= X[p]){
            A[k] = L[i];
            ++i;
        }else if(R[j] <= X[p]){
            A[k] = R[j];
            ++j;
        }else{
            A[k] = X[p];
            ++p;
        }
    }
}

void Mergesort(register int front, register int rear){
    /*
     * Check if there is only One element in array
     */
    if(front < rear){
        /*
         * calculate the size of 1/3 of array
         * Now calculate two mid points since it is 3 way partition
         */
        register int dist = (rear - front + 1) / 3;
        int mid1 = front + dist;
        int mid2 = mid1 + dist;

        /*
         * Recursively call this array cutting down original array by 1/3 ( One Third )
         */
        Mergesort(front, mid1);
        Mergesort(mid1 + 1, mid2);
        Mergesort(mid2 + 1, rear);

        /*
         * Merge divided elements back into original array
         */
        Merge(front, mid1, mid2, rear);
    }
}

int main(){
    register int n, i;
    while(scanf("%u", &n) && n){
        for(i = 0; i < n; ++i)
            scanf("%u", &A[i]);

        /*
         * Merge sort from index 0 to index n-1
         */
        Mergesort(0, n - 1);

        for(i = 0; i < n; ++i){
            printf("%u", A[i]);
            /*
             * For the last sorted element do not print a space
             */
            if(i != n-1)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

 Quick Sort Code ( 2 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Quick Sort ( 2 Partition )
 */
#include<cstdio>
#include<iostream>

#define SIZE 2000002

static int A[SIZE];

void quicksort (int *a, register int n) {
    register int i, j, mid;
    if (n < 2) return;

    mid = a[n >> 1];

    for (i = 0, j = n - 1; ; i++, j--) {
        while (a[i] < mid)
            i++;
        while (mid < a[j])
            j--;

        if (i >= j) break;
        std::swap(a[i], a[j]);
    }
    quicksort(a, i);
    quicksort(a + i, n - i);
}

int main () {
    register unsigned n, i;
    while(scanf("%u", &n) && n){
        for(i = 0; i < n; ++i)
            scanf("%d", &A[i]);

        quicksort(A, n);

        for (i = 0; i < n; i++)
            printf("%d%s", A[i], i == n - 1 ? "\n" : " ");

    }
    return 0;
}

 Quick Sort Code ( 3 Partition ):

/* To Do */

UVA Problem 100 – The 3n + 1 problem Solution

UVA Problem 100 – The 3n + 1 problem Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is not for beginners. Due to a simple logical error I failed and failed again.

Before proceeding to understand my solution please check Memoization, Lookup Table, Recursion, Dynamic Programming, Bitwise Operations. Also you may check Algorithmist Solution and Collatz Conjecture. Learned this solution technique is from here.

For this problem we are given two numbers. We need cycle from and including the smaller number to and including the bigger number.

Basically we are to cycle through the given range and find the maximum cycle length among all numbers in the given range.

Here i have used a lookup table to store already calculated cycle lengths. This dramatically decreases running time. Without lookup table my first solution took 0.552 s but when i applied memoization ( this solution ) took only 0.035 s.

0.552 > 0.035 /* See the speed difference */

Another thing is when the number is ODD we need to calculate 3*n+1. But when we calculate 3*n+1 for any ODD number the ODD number becomes EVEN. Now we can divide by 2 in same step since it becomes EVEN. So here i performed 2 steps in the ODD checking code.


 

n = 3, 3*n+1 = 10 /* So calculating 3n+1 for odd number is always even */
n = 7, 3*n+1 = 22 /* Since it becomes even we can perform n/2 in same step */

 

Also another thing to note is that i used,

n >> 1 /* Which does the same thing as n/2 but Faster */

 

So here I calculate the cycle length and store them in table. If the table already contains the definition it returns the cycle length to main(). There I check if the returned cycle length is bigger then existing max cycle length.

Last thing set the first index of table to 1 since I haven’t used any condition to check if the number becomes 1. Also it is much faster than checking every time since the number is bound to converge in 1. So 1 is stored in look table when it is found its immediately returned.

table[1] = 1;

Rest i explained code comments. Hopefully it is easier to understand :).

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

1 10
100 200
201 210
900 1000

Output:

1 10 20
100 200 125
201 210 89
900 1000 174

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 100 ( 3n + 1 )
 */
#include<stdio.h>

#define SIZE 1000002

/* Lookup table for storing previously calculated values */
static unsigned table[SIZE];

/* Returns cycle length for given number */
unsigned cycleLength(register unsigned n){
    /* If the value already exists in the lookup table then return its cycle length */
    if (n < SIZE && table[n])
        return table[n];

    /* Check if number is odd */
    if (n&1){
        if (n < SIZE){
            /* Since 3n+1 becomes an even number, we perform the next step which is divided by two since its even, also +2 since we perform two operations */
            table[n] = 2 + cycleLength((3 * n + 1) >> 1);
            return table[n];
        }else
            /* The value is bigger than table so we calculate and return */
            return 2 + cycleLength((3 * n + 1) >> 1);
    }else{
        if (n < SIZE){
            /* The number is even so we perform number divided two, or bit shift left once */
            table[n] = 1 + cycleLength(n >> 1);
            return table[n];
        }else
            return 1 + cycleLength(n >> 1);
    }
}

int main(){
    unsigned a, b, count;
    register unsigned n;
    /* This is necessary since i don't check for 1 in cycleLength, Also 1st index is always 1 */
    table[1] = 1;

    while (scanf("%u%u", &a, &b) == 2){
        unsigned maxCycle = 0;
        /* The input may contain bigger number first then smaller number */
        if (a < b){
            for (n = a; n <= b; ++n){
                /* Cycle every value between a to b */
                count = cycleLength(n);
                /* We need to find max cycle, so if a cycle count is greater than maxCycle then replace maxCycle */
                if (maxCycle < count)
                    maxCycle = count;
            }
        }else{
            for (n = b; n <= a; ++n){
                count = cycleLength(n);
                if (maxCycle < count)
                    maxCycle = count;
            }
        }
        printf("%u %u %u\n", a, b, maxCycle);
    }
    return 0;
}

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print:

Code Explanation:

This code is bit complex and will require knowledge on:

  1. Struct
  2. Linked list
  3. Queue
  4. Stack
  5. Binary Tree ( check this and this too  )

Input Format:

Level Order tree input style
Level Order tree input style
binary Tree Graph sample Input for the console picture shown above
binary Tree Graph sample Input for the console picture shown above

Code:

/*
 * Author: Quickgrid
 * Code: Tree creation, traversal in array & linked list ( inorder/preorder/postorder/levelorder )
 * Description:
 */

#include <stdio.h>

#define size 1000   /* used this for queue array */

struct tree{    /* binary tree structure */
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree node;

struct stack{   /* linear/singly linked list stack to hold tree type data */
    node *nodedata;
    struct stack *next;
};
typedef struct stack vertex;

node* q[size];  /* here our array is node data type that we defined above */
int f = 0, r = 0;
vertex *front = NULL, *rear = NULL;
node *root = NULL;

void enq(node *root){   /* circular queue array modular arithmetic */
    int s = (r+1) % (size+1); /* +1 means we don't use 1 box of the array */
    if(f == s){
        printf("Queue Full.\n");
        return;
    }
    q[s] = root; /* root is node type we put it in our node array */
    r = s;  /* s is temporary variable */
}

node *deq(){
    if(f==r){
        printf("Queue Empty.\n");
        return NULL;
    }
    f = (f+1)%(size+1);
    node *temp = q[f]; /* get the last element of the queue to return for further operations */
    q[f] = 0;
    return temp;
}

void levelOrderArray(node *root){
    enq(root);  /* here we enqueue the root or the node that we want to star from */
    while(f!=r){ /* check if our queue is not empty */
        node *v = deq(); /* dequeue one item */
        printf("%c ", v->data);
        if(v->left!=NULL){ /* check if left branch of tree exists */
           enq(v->left); /* send the left node to queue */
        }
        if(v->right!=NULL){ /* check if right branch of tree exists */
            enq(v->right); /* send the right node to queue */
        }
    }
}

void enqueue(node *root){   /* enqueue function for our stack in linked list */
    if(front == NULL){
        front = new vertex();
        front->nodedata = root;
        front->next = NULL;
        rear = front;
    }else{
        vertex *temp = new vertex();
        temp->nodedata = root;
        temp->next = NULL;
        rear->next = temp;
        rear = temp;
    }
}

vertex *dequeue(){
    if(front == NULL){
        printf("queue empty.\n");
        return front;
    }
    vertex *temp,*tmp = front;
    front = front->next;
    delete temp;
    return tmp;
}

void levelorder (node *root){
    enqueue(root);
    while ( front != NULL ){
        vertex *v = dequeue();  /* we dequeue one vertex type data from our vertex stack */
        if(v!=NULL){
            printf("%c",v->nodedata->data);

            if (v->nodedata->left != NULL){ /* nodedata is our data part which holds node type data */
                enqueue(v->nodedata->left);
            }
            if (v->nodedata->right != NULL){
                enqueue(v->nodedata->right);
            }
        }
    }
}

int treeHeight(node *root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight){
        return leftHeight+1;
    }else{
        return rightHeight+1;
    }
}

void printGivenLevel(node *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%c ", root->data);
    }else if(level > 1){
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void createBinaryTree (node *root)
{
    char ans;

    fflush(stdout);
    printf("%c has any left child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create left side of a tree node */
    {
        root->left = new node ();
        root->left->left = NULL;
        root->left->right = NULL;
        fflush(stdout);
        printf("Enter left data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->left->data);
        createBinaryTree (root->left);  /* recursive call with created node as root to check if it has left and right */
    }

    fflush(stdout);
    printf("%c has any right child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create right side of a tree node */
    {
        root->right = new node ();
        root->right->left = NULL;
        root->right->right = NULL;
        fflush(stdout);
        printf("Enter right data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->right->data);
        createBinaryTree (root->right);
    }
}

void postOrder(node *root){
    if(root->left!=NULL){
        postOrder(root->left);
    }
    if(root->right!=NULL){
        postOrder(root->right);
    }
    printf("%c ", root->data);
}

void preOrder(node *root){
    printf("%c ", root->data);
    if(root->left!=NULL){   /* check if left side of that node exist */
        preOrder(root->left);   /* recursive call of preorder using this node as the root */
    }
    if(root->right!=NULL){
        preOrder(root->right);
    }
}

void inOrder(node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%c ", root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
}

int main ()
{
    char ans;
    fflush(stdout);
    printf("Do u want to create a tree: ");
    fflush(stdin);
    ans = getchar();

    root = new node ();
    fflush(stdout);
    printf("Enter root of tree: ");
    fflush(stdin);
    scanf("%c",&root->data);
    createBinaryTree(root);

    int height = treeHeight(root);
    printf("\nTree Height: %d", height);

    printf("\nLevel order Linked List: ");
    levelorder(root);   /* Instead of sending root we can send another node to level order from that node */
    printf("\nLevel order Array: ");
    levelOrderArray(root);
    printf("\nPre order : ");
    preOrder(root);
    printf("\nIn order : ");
    inOrder(root);
    printf("\nPost order : ");
    postOrder(root);

    printf("\nEnter level to print:");
    int level;
    scanf("%d", &level);
    if(level >= height || level < 1){
        printf("\nGiven level doesn't exist.");
    }else{
        printf("Level %d: ", level);
        printGivenLevel(root, level);
        printf("\n");
    }
    return 0;
}