Hamming Numbers

This exercise is taken from www.programmingpraxis.com
=========================================================
"The sequence of Hamming numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, … (A051037) consists of all numbers of the form 2i·3j·5k where i, j and k are non-negative integers. Edsger Dijkstra introduced this sequence to computer science in his book A Discipline of Programming, and it has been a staple of beginning programming courses ever since. Dijkstra wrote a program based on three axioms:

Axiom 1: The value 1 is in the sequence.

Axiom 2: If x is in the sequence, so are 2 * x, 3 * x, and 5 * x.

Axiom 3: The sequence contains no other values other than those that belong to it on account of Axioms 1 and 2.

Your task is to write a program to compute the first thousand terms of the Hamming sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below."
=========================================================

Here is my C solution

=========================================================

#include 
#include 

int ham_num(int x) {
    int h = x;
    while (h && (h%2 == 0)) 
        h = h/2;

    while (h && (h%3 == 0)) 
        h = h/3;
    
    while (h && (h%5 == 0)) 
        h = h/5;
   /* 
    * h will be 1, when it is ham num, else it will be  
    * something else - example h =10  
    */
   return h;
}

int main(int argc, char *argv[])
{
    int x = 1, cnt = 1000;
    printf("Hamming Numbers : \n");
    if (argc > 1)  
        cnt = atoi(argv[1]); 

    while (cnt) {
        if (ham_num(x) == 1) {
            printf("%d ",x);
            cnt--;
        }   
        x++;
    }   
    printf("\n");
}

Snapper Chain!! - Google codejam-2010

http://code.google.com/codejam/contest/dashboard?c=433101#s=p0

You can find the problem description above! Believe me it's so much of fun to solve this!!
Go ahead and try!!!! I could not believe after I got the solution!.....Ufffff.......

Hint :: Think in bits!!

Approach ::
Lets say we have 2 snappers (N =2)-
Initially both are in OFF state

Remember : With a snap, only the snapper receiving power changes state!!!

OFF	OFF	Initial State
ON	OFF	After snap k =1
OFF	ON	After snap k =2
ON	ON	After snap k =3
OFF	OFF	Snap k =4

See the bit pattern ?? Lets say OFF = 0; and ON = 1

0	0	Initial State K=0
1	0	K=1
0	1	K=2
1	1	K=3
0	0	K=4

So, if there are N snappers, we will turn the light on when K = [2 (power) N ] - 1
In the above case, N = 2, K = pow(2,2)-1 = 3. , After that, a snap will get us to the initial state!!

Isn't it simple and great!!!!!!!!

===================================================

int main () {
   int n,k,num_cases;
   int factor,i;
   FILE *fp;

   fp = fopen("A-large-practice.in","r");
   if (!fp) {
      exit(0);
   }
   fscanf(fp,"%d",&num_cases);
   for (i = num_cases ; i > 0; i--) {
      fscanf(fp,"%d %d", &n, &k);
      factor = pow(2,n);

      printf("Case #%d: ",num_cases-i+1);
      if (k%factor == (factor-1))
          printf("ON\n");
      else
          printf("OFF\n");

   }
 fclose(fp);

}

First non repeating character in a string

Problem taken from http://programmingpraxis.com/
=================================================
Write a function that takes an input string and returns the first character from the string that is not repeated later in the string. For instance, the two letters “d” and “f” in the input string “aabcbcdeef” are non-repeating, and the function should return “d” since “f” appears later in the string. The function should return some indication if there are no non-repeating characters in the string.
=================================================

Here is my solution ::
-- I am going over the length of the string, breaking whenever I find a non-repeating char.
For ease of searching a char, I am copying the entire string, expect the "char" I am currently looking at to a new string and search for that char in the new appended string.
If found implies it's repeated, else non-repeating

<pre class="prettyprint">

int main () {

    char str[80];
    char str_a[80];
    int len, i;
    char c;

    printf("Please enter the string to find non-repeating char\n");
    scanf("%s",str); 
    len = strlen(str);

    for (i = 0; i < len ; i++) {
        c = str[i];
       //copy rest of the string except char 'c' into another
        memcpy(&str_a[0] , &str[0], i); 
        memcpy(&str_a[i] , &str[i+1], (len-i-1));
        if (!strchr(str_a, c)) {
            printf("First non repeating char in string : \"%c\"\n",c);
            break;
        }   
    }   
    if (i == len)
        printf("Non repeating char not found in given string\n");
}

String reversal with words in tact!!

I am on a freaking C programming spirit for past two days!! I feel like coding all the way!!

Problem statement
===============================================

Reverse a string with words, with words intact. 

Example will make it explain better 

Input string:: "I am a programming freak!"
Output :: "freak! programming a am I" 



Another -- "I use Mac book" i.e. "book Mac use I"
===============================================
Here is my working Solution!!
===============================================

<pre class="prettyprint">

int main()
{
    char *orig_str = NULL;
    char *rev_str;
    char str[80]; //This is a limitation right now
    char delims[] = " ";
    int orig_len,len =0,slen =0;

    printf("Please enter the string you want to reverse in words\n");
    fgets(str, 80, stdin); //fgets has ugly trailing '\n' too
    len = strlen(str);
    
    if (str[len-1] == '\n')
        str[len-1] = '\0';

    orig_len = len = strlen(str); //new str len with out \n

    rev_str = (char *)malloc(len+1);
    rev_str[len] = '\0';

    orig_str = strtok(str, delims);
    while (orig_str != NULL) {
            slen = strlen(orig_str);
    
            //this to prevent adding space for the first word
            //in orig_str which will be the last in rev_str
            if (len < orig_len)
               strncpy(&rev_str[len]," ",1);

            len = len - slen;
            strncpy(&rev_str[len],orig_str,slen);

            len--;  // for space added to the rev_str

            orig_str = strtok(NULL,delims);
    }
    printf("\nString reversed in words is :\"%s\"\n",rev_str);
    free(rev_str);
}

Cyclic Sorted List

Problem from : http://programmingpraxis.com/
=====================================================
Given a node from a cyclic linked list which has been sorted,
write a function to insert a value into the list such that it
remains a cyclic sorted list. The given node can be any single node
in the list
=====================================================

This problem got my attention as I am kinda fond of lists.
I worked out my logic, this way

1) If node passed in is NULL, => no elements so far in list.
create a new node and back point to itself
2) first and last elements of list i.e. highest or lowest (could be equal too)
It should be inserted at the end or beginning (both same as it's cyclic list)
3) Any other element to be inserted in the middle (could be equal to one of the elements)
find prev->elem <= elem_to_insert <= next->elem

Tricky part I find here is, for cases (2) and (3), we might have to get to the starting point of the list. This is because we are given some random node as input, not the head node. So, element we need to insert might just happen go before the input node. So, we start from input node and make a loop through all the nodes until we hit the same input node again.

After going over and going over again to crisp it(;), here is my solution!

=====================================================

<pre class="prettyprint">

typedef struct node_ {
    int x;
    node *next;
} node_t;


node_t* create_node(node_t *node_next,int to_insert) {
    node_new = malloc(sizeof(struct node_));
    if (node_new != NULL) {
        node_new->x = to_insert;
        node_new->next = node_next;
    } else {
         printf("\n Malloc failed. \n");
         exit(0);
    }   
    return node_new;
}

node_t *insert_node(node_t *curr, int i) {
    node_t *node_new=NULL, *prev=NULL,*given_node;
    given_node = curr;
    if (curr == NULL) {
        //empty list
        node_new = create_node(curr,to_insert);
        node_new->next = node_new; //point to itself
    } else { //not an empty list
        do {
            prev = curr;
            curr = curr->next;

            /* insert at beginning or end - highest or lowest */
            if ((prev->x > curr->x)  &&
                 (i >= prev->x || i <= curr->x))
                 break;

            /* insert in between */
            if ( i >= prev->x && i <= curr->x)
                break;
        }  while (curr != given_node);

        node_new = create_node(curr,i);
    }
    return node_new;
}