Count Loose Change

Problem: Counts changes using minimum number of coins.
Solution:read

#include <iostream>
#include <string>
using namespace std;

/**
 ******************************************************************************
 *
 * Counts the minimum number of coins to add up to sum.
 * 
 * @param argc 
 * @param argv 
 * 
 * @return int 
 *
 ******************************************************************************
 */
int main (int argc, char *argv[])
{
    enum
    {
        QUARTER = 25,
        DIME    = 10,
        NICKEL  = 5,
        PENNY   = 1
    };

    string amount, amountSaved;
    int ones = 0, tenths = 0, dollars = 0;

    cout << "This program calculates the minimum number of coins to make change in coins" << endl;
    cout << "Enter a $ amount (e.g. 1.2 for one dollar 20 cents):$ ";
    cin >> amount;

    dollars = atoi(&amount[0]);

    // Checks for a decimal point
    size_t pos = amount.find(".");
    if (amount.npos != pos)
    {
        size_t trail = amount.size() - 1;   // excludes decimal point
        if (trail > 2)
        {
            amount.erase(pos+3);    // erase chars after 2 decimal digits
        }
        amountSaved = amount;   // save a copy
    
        ones = atoi(&amount[pos+2]);
        amount[pos+2] = '\0';
        tenths = atoi(&amount[pos+1]);
    }
    unsigned int total = static_cast<unsigned int>(dollars * 100 + tenths * 10 + ones);

    int denom[] = {QUARTER, DIME, NICKEL, PENNY};
    const int nDenom = sizeof(denom) / sizeof(int);
    int count[nDenom] = {0, 0, 0, 0};
    int coins = 0;

    // Using Greedy algorithm 
    while (total)
    {
        if (total >= denom[coins])
        {
            count[coins]++;
            total -= denom[coins];
        }
        else
        {
            coins++;
        }
    }

    cout << "Number of coins for $ " << amountSaved << " is:\n";
    cout << count[0] << " quarters" << endl;
    cout << count[1] << " dimes"    << endl;
    cout << count[2] << " nickels"  << endl;
    cout << count[3] << " pennies"  << endl;
    return 0;
}
// Original solution provided by Jeff Fore.
hide solution

Count Set Bits

Problem: Count number of set bits in a 32-bit number.
Solution:read

#include <iostream>
using namespace std;

/**
 ******************************************************************************
 *
 * Counting set bits in a 32-bit number 
 * 
 * @param v 
 * 
 * @return unsigned int 
 *
 ******************************************************************************
 */
unsigned int CountBits(unsigned int v)
{
    v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
}

/**
 ******************************************************************************
 *
 * Count number of set bits in a 32 bit number. 
 * 
 * Reference: http://graphics.stanford.edu/~seander/bithacks.html
 * 
 * @return int 
 *
 ******************************************************************************
 */
int main(int argc, char *argv[])
{
    unsigned int val;

    cout << "Please enter a hex number\n:";
    cin >> hex >> val;
    cout << hex << CountBits(val) << " bits are set in " << val << endl;
    return 0;
}
// This solution is kindly provided by Jeff Fore.
hide solution

Find Max Sum

Problem: Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. For example,

• 3 2 7 10 should return 13 (sum of 3 and 10)
  
• 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

Solution:read

#include <iostream>
using namespace std;

void findMaxSum(int buf[], size_t cnt);
void findMaxInterlacedSum(int *buf, size_t cnt);

/**
 ******************************************************************************
 *
 * Given an array all of whose elements are positive numbers, find the maximum 
 * sum of a subsequence with the constraint that no 2 numbers in the sequence 
 * should be adjacent in the array. For example,
 *
 * i) 3 2 7 10 should return 13 (sum of 3 and 10)
 * ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7) 
 * 
 * Reference:
 * http://stackoverflow.com/questions/584228?sort=newest#sort-top
 *
 * @param argc 
 * @param argv 
 * 
 * @return int 
 *
 ******************************************************************************
 */
int main (int argc, char *argv[])
{
    int array1[] = { 3, 2, 7, 10 };
    int array2[] = { 3, 2, 5, 10, 7 };
    int array3[] = { 3, 7, 2, 10, 9, 1 };

    findMaxInterlacedSum(array1, sizeof(array1)/sizeof(int));
    findMaxInterlacedSum(array2, sizeof(array2)/sizeof(int));
    findMaxInterlacedSum(array3, sizeof(array3)/sizeof(int));

    cout << endl << "findMaxSum . . ." << endl;

    findMaxSum(array1, sizeof(array1)/sizeof(int));
    findMaxSum(array2, sizeof(array2)/sizeof(int));
    findMaxSum(array3, sizeof(array3)/sizeof(int));

    return(0);
}

/**
 ******************************************************************************
 *
 * Finds maximum sum from any numbers as long as they are not adjcent numbers. 
 * 
 * @param buf 
 * @param cnt 
 *
 ******************************************************************************
 */
void findMaxSum(int buf[], size_t cnt)
{
    int incl = 0;   // max sequence including the previous item
    int excl = 0;   // max sequence excluding the previous item
    int excl_new=0;

    for (size_t i = 0; i < cnt; i++)
    {
        //cout << buf[i] << ", " << ((i+1 < cnt) ? buf[i+1] : 0) << ", ";

        // current max excluding i
        if (incl > excl)
        {
            excl_new = incl;
        }
        else
        {
            excl_new = excl;
        }

        // current max including i
        incl = excl + buf[i];
        excl = excl_new;

        //printf("incl=%d, excl=%d, excl_new=%d\n", incl, excl, excl_new);
    }
    cout << "\nmax sum = " << ((incl > excl)? incl : excl) << endl;
}

/**
 ******************************************************************************
 *
 * Finds maximum sum in an interlaced fashion. 
 * 
 * @param buf 
 * @param cnt 
 *
 ******************************************************************************
 */
void findMaxInterlacedSum(int *buf, size_t cnt)
{
    int sumE = 0;
    int sumO = 0;

    for (size_t i=0; i < cnt; i+=2)
    {
        cout << buf[i] << ", " << ((i+1 < cnt) ? buf[i+1] : 0) << ", ";

        sumE += buf[i];
        if (i+1 < cnt) sumO += buf[i+1];
    }
    cout << "\nmax interlaced sum = " << ((sumE > sumO)? sumE : sumO) << endl;
}
// This solution is kindly provided by Jeff Fore.
hide solution

Linked List Problems

Problem: Reverses a singly linked list.
Solution:read

#include <iostream>
using namespace std;

struct node
{
    char c;
    node *next;
};

node *buildlist(char *);
node *revlist(node *);
void freelist(node *);

/**
 ******************************************************************************
 *
 * Reverses a singly linked list
 * 
 * @param argc 
 * @param argv 
 * 
 * @return int 
 *
 ******************************************************************************
 */
int main (int argc, char *argv[])
{
    char buf[128];
    char *str = buf;
    
    cout << "Enter string:";
    str = fgets(buf, 127, stdin);

    if (str)
    {
        size_t len = strlen(str) -1;    // subtract line feed
        str[len] = '\0';                // strip line feed
        printf("in (%03d): %s\n", len, str);

        node *p = buildlist(str);
        node *phead = revlist(p);

        printf("out(%03d): ", len);
        p = phead;
        while (p != NULL)
        {
            printf("%c", p->c);
            p = p->next;
        }
        printf("\n");

        freelist(phead);
    }
    return(0);
}

/**
 ******************************************************************************
 *
 * Builds a singly linked list from the string
 * 
 * @param str 
 * 
 * @return node* pointing to the head of list
 *
 ******************************************************************************
 */
node *buildlist(char *str)
{
    node *head = NULL;
    if (str)
    {
        node *p = new node;
        if (p != NULL)
        {
            head = p;
            p->c = *str++;
            p->next = NULL;

            node *q;
            while (*str != '\0')
            {
                q = new node;
                if (q != NULL)
                {
                    q->c = *str++;
                    q->next = NULL;
                    p->next = q;
                    p = q;
                }
                else {
                    printf("Cannot allocate node\n");
                    break;
                }
            }
        }
        else {
           printf("Cannot allocate head node\n");
        }
    }
    return head;
}

/**
 ******************************************************************************
 *
 * Frees all the nodes in the list
 * 
 * @param p - pointer to head of list
 *
 ******************************************************************************
 */
void freelist(node *p)
{
    node *q;
    while (p != NULL)
    {   
        q = p->next;
        delete p;
        p = q;
    }
}

/**
 ******************************************************************************
 *
 * Reverse the list
 * 
 * @param p - pointer to head of list
 *
 * @return node* pointing to the head of reversed list
 *
 ******************************************************************************
 */
node *revlist(node *p)
{
    node *cur = NULL;

    if (p != NULL)
    {
        node *nxt;
        node *old;

        // initializes local pointers
        cur = old = p;
        nxt = p->next;

        p->next = NULL;         // root becomes tail, sets root->next to null

        while (nxt != NULL)
        {
            cur = nxt;          // operates on this node
            nxt = cur->next;    // advances nxt pointer
            cur->next = old;    // reverses link - points to previous node
            old = cur;          // old points to head node of reversed list
        }
    }
    return cur;                 // points to head of reversed list
}
hide solution

String Manipulations

Problem: Reverses a character string in place.
Solution:read

#include <iostream>
using namespace std;

char *revstr(char * str);

/**
 ******************************************************************************
 *
 * Reverses character string in place
 * 
 ******************************************************************************
 */
int main (int argc, char *argv[])
{
    char buf[128];
    char *str = buf;
    
    cout << "Enter string:";
    str = fgets(buf, 127, stdin);

    if (str)
    {
        size_t len = strlen(str) -1;    // subtract line feed
        str[len] = '\0';                // strip line feed
        printf("in (%03d): %s\n", len, str);
        printf("out(%03d): %s\n", len, revstr(str));
    }
    return(0);
}


/**
 ******************************************************************************
 *
 * Reverses character string in place
 * 
 * @param str 
 * 
 * @return char* 
 *
 ******************************************************************************
 */
char *revstr(char *str)
{
    if ( (str!=NULL) && (*str!='\0') )
    {
        size_t len = strlen(str);

        char *start, *end;
        start = str;
        end = &str[len-1];  // adjust index to zero base
        for(size_t i=0; i<len/2; i++)
        {
            *start ^= *end;
            *end   ^= *start;
            *start++ ^= *end--;
        }
    }
    return str;
}
hide solution

Search Problems

Problem: Removes duplicate numbers in a sorted array and shrinks array if duplicates are found.
Solution:read

#include <iostream>
using namespace std;

template <typename AT, typename AS>
void inline printArray(AT p[], AS len)
{
    for (size_t i=0; i<len; i++) {
        cout << p[i] << " "; 
    }
    cout << endl;
} 

size_t unique(int *p, size_t len);

/**
 ******************************************************************************
 *
 * Removes duplicate numbers in a sorted array and shrinks array if duplicates
 * are found
 * 
 ******************************************************************************
 */
int main (int argc, char *argv[])
{
    int testa[]= { 1, 2, 4, 6, 7, 8, 9, 12, 15, 19 };
    int testb[]= { 1, 1, 1, 4, 5, 9, 9, 10, 10, 12, 15, 18, 20 };
    int testc[]= { 1, 2, 4, 5, 6, 8, 8, 8, 8, 8 };
    int *p;
    size_t len;

    p = testa;
    len = sizeof(testa)/sizeof(int);
    len = unique(p, len);
    printArray(p, len);

    p = testb;
    len = sizeof(testb)/sizeof(int);
    len = unique(p, len);
    printArray(p, len);

    p = testc;
    len = sizeof(testc)/sizeof(int);
    len = unique(p, len);
    printArray(p, len);

    return(0);
}

/**
 ******************************************************************************
 *
 * Removes duplicate numbers and shrinks array if duplicates are found
 * 
 * @param p   - pointer to array
 * @param len - original size of array
 * 
 * @return new length of array 
 *
 ******************************************************************************
 */
size_t unique(int *p, size_t len)
{
    size_t newLen = len;

    if (p != NULL)
    {
        int *q = p;

        // prints original content
        printArray(q, len);
   
        // camera and action!
        int cval = *p;
        int *vs, *nxt;  // pointer to vacated slot and next number

        vs = nxt = p+1;
    
        for (size_t i=0; i<len; i++, nxt++)
        {
            if (cval != *nxt)
            {
                cval = *nxt;
                if (vs != nxt)
                {
                    *vs = cval;
                }
                vs++;
            }
            else {
                newLen--;
            }
        }
    }
    return newLen;
}
hide solution

Search Problems

Problem: Given an array of size n, which contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
Solution:read

#include <iostream>
#include <bitset>
using namespace std;

//Given an array of size n. It contains numbers in the range 1 to n. 
//Each number is present at least once except for 2 numbers. 
//Find the missing numbers.

static const int N = 10;

int main()
{
    int numArray[N] = { 1, 7, 3, 4, 6, 2, 9, 9, 10, 10 };
    bitset<N> bits;

    bits.set();

    for (int i = 0; i < N; i++)
    {
        // Clears bit that corresponds to the number; bit array is zero based
        bits.set(numArray[i] - 1, false);
    }

    for (int i = 0; i < N; i++)
    {
        if (bits.test(i)) {
            printf("Found unused value %d\n", i + 1);
        }
    }
    return 0;
}
//This solution is kindly provided by Jeff Fore.
hide solution

Back to Basics

Problem: How to detect stack growth direction and platform endianess?
Solution:read

#include <iostream>
using namespace std;

void stackdir(int i);
void printEndian(void);

/**
 ******************************************************************************
 *
 * Prints stack growth direction and platform endianess
 * 
 ******************************************************************************
 */
int main(int argc, char *argv[])
{
    stackdir(10);
    printEndian();
    return(0);
}

/**
 ******************************************************************************
 *
 * Prints stack growth direction
 * 
 ******************************************************************************
 */
void stackdir(int i)
{
    int j;

    cout << "-----------------------" << endl;
    cout << "[stack direction . . .]" << endl;
    printf("param=%p, local=%p\n", &i, &j);

    if (&j < &i) {
        printf("grows down\n");
    }
    else {
        printf("grows up\n");
    }

    j=0;
}

/**
 ******************************************************************************
 *
 * Prints platform endianess 
 * 
 ******************************************************************************
 */
void printEndian()
{
    cout << "-----------------------" << endl;
    cout << "[endianess . . .]" << endl;

    int i = 1;
    char *p = reinterpret_cast<char *>(&i);

    if (p[0] == 1) {
      // Lowest address contains the least significant byte
      cout << "little endian" << endl;
    }
    else { 
      cout << "big endian" << endl;
    }
}
hide solution