Binary Search Tree

/* Binary Search Tree */

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>
#include <stdlib.h>

struct tree_node
{
     struct tree_node *left ;
     struct tree_node *right ;
     struct tree_node *parent ;
     int key ;
};

typedef struct tree_node *TREENODEPTR ;

TREENODEPTR bst_search(TREENODEPTR r, int k)
{
     while (r != NULL && k != r->key)
          if (k < r->key)     r = r->left ;
          else r = r->right ;

     return r ;
}

/* 
     r : points to root of the tree
     n : pointer to the new node to be inserted
*/
void bst_insert(TREENODEPTR *r, TREENODEPTR n)
{
     TREENODEPTR p = NULL ;
     TREENODEPTR x = *r ;

     while (x != NULL) {
          p = x ;
          if (n->key < x->key)
               x = x->left ;
          else x = x->right ;
     }

     n->parent = p ;
     if (p == NULL)
          *r = n ;
     else if (n->key < p->key)
          p->left = n ;
     else p->right = n ;
}

void clear(TREENODEPTR r)
{
   if (r==NULL)
      return ;

   if (r->left) clear(t, r->left) ;
   if (r->right) clear(t, r->right) ;

   free(r) ;
}

int main()
{
     int n ;
     TREENODEPTR root, tmp ;

     #ifndef ONLINE_JUDGE
     freopen("bst.in", "r", stdin) ;
     #endif

     root = NULL ;

     while (scanf("%d", &n) != EOF) {
          if ((tmp = bst_search(root, n)) == NULL) {
               tmp = (TREENODEPTR) malloc(sizeof(struct tree_node)) ;
               tmp->key = n ;
               tmp->left = NULL ;
               tmp->right = NULL ;
               tmp->parent = NULL ;
               bst_insert(&root, tmp) ;
          }
          else {
               printf("Element [%d] already exists\n", n) ;
          }
     }

     if (root) {
          clear(root) ;
          free(root) ;
     }

     return 0;
}

/* @END_OF_SOURCE_CODE */

Difference in time

/* 
   Returns difference in time between a given start hour, 
   start min and end hour and end min 
*/

int difftime(int sh, int sm, int eh, int em)
{
   int s, e ;
   s = 60*(sh-0) + sm ;
   e = 60*(eh-0) + em ;
   e -=s ;

   if (e < 0)
   e += 60 * 24 ;
   return e ;
}

Josephus Problem

Given n (number of people) and m (every mth person eliminated), this code returns the index of the last person to be eliminated.

Josephus on wiki
Josephus on Wolfram MathWorld

/* Josephus Problem */

#include <stdio.h>

#define CAL_UPTO     100000

int cq[CAL_UPTO + 1] ;

/* count e from p and return new p */
int move(int e, int p, int left, int n)
{
     if (e==0) e=left ;

     while (e>0) {
          if (p>n) p = 1 ;
          if (cq[p]==1) e-- ;
          p++ ;
     }

     if (--p>n) p=1 ;
     return p ;
}

/* out of n persons, eliminate every mth person */
/* returns the last survisor */
int compute(int n, int m)
{
     int i, p=1, e, left=n, j ;

     for (j=1; j<=n; j++) cq[j] = 1 ;

     while (left) {
          e = m%left ;
          p = move(e, p, left, n) ;
          if (!(p==0 || cq[p]==0)) cq[p] = 0, left-- ;
     }
     return p ;
}

int main()
{
     int i, j, n, k ;

     scanf("%d%d", &n, &k) ;
     printf("Survivor: %d\n", i, compute(n, k)) ;

     return 0;
}

Prime Number Generator

The function sieveOfAtkin() generates all primes numbers up to (less than) the integer PRIMES_UPTO.

For an explanation of Sieves of Atkin method, see here. Also see Sieve of Eratosthenes of which Sieve of Atkins is an optimized version.

#include <stdio.h>
#include <math.h>

#define PRIMES_UPTO     100

int list[PRIMES_UPTO+1]={0,0,1,1},n;
int primes[PRIMES_UPTO] ;

/* flip() and clean() are supporting routines called by sieveOfAtkin()
*/
int flip(void)
{
     if (list[n]==1) list[n]=0;
     else list[n]=1;
     return 0;
}

int clean(int n, int upto)
{
     int k,l=n*n,i;
     for (i=2,k=l;k<=upto;i++,k=i*l) list[k]=0;
     return 0;
}

/* Generates prime numbers upto the integer specified by PRIMES_UPTO.
    Stores the result in the array primes[] and returns index of the
    last prime number in the sequence.
*/
int sieveOfAtkin(void)
{
     int i, j, x, y, d_limit;

     d_limit=(int)(sqrt((float) PRIMES_UPTO));

     for (i=5;i<=PRIMES_UPTO;i++) list[i]=0;

     for (x=1;x<=d_limit;x++) {
         for (y=1;y<=d_limit;y++) {
             n=4*(x*x)+(y*y);
             if (n <= PRIMES_UPTO && (n % 12 == 1 || n % 12 == 5)) flip();

             n=3*(x*x)+(y*y);
             if (n <= PRIMES_UPTO && n % 12 == 7) flip();

             n=3*(x*x)-(y*y);
             if (x>y && n <= PRIMES_UPTO && n % 12 == 11) flip();
         }
     }

     for (n=5;n<=d_limit;n++) {
         if (list[n]) clean(n,PRIMES_UPTO);
     }

     for (i=2, j=0;i<=PRIMES_UPTO;i++) {
         if (list[i]) primes[j++] = i ;
     }

     return j-1 ;
}

int main()
{
     int i, k ;

     printf("Prime numbers between 0 and %d:\n", PRIMES_UPTO) ;
     k = sieveOfAtkin() ;
     for (i=0; i<=k; i++)
          printf("%d\n", primes[i]) ;

     return 0;
}

Maximum 1-D Sum

#include <stdio.h>
#define MAX_N     100

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

/*
  * Problem - Maximum Value Contiguous Subsequence / Maximum 1-D sum
  * From a sequence of n integers a(1) ... a(n), determine a 
  * contiguous sub-sequence a(i) ... a(j) having the maximum sum of 
  * its elements.
  *
*/
int dp_max_contiguous_subseq(int *arr, int len)
{
     int i, j, m[MAX_N], max,
          s=0,     /* index of start of the sub-sequence */
          e=0 ;     /* index of end of the sub-sequence */

     if (arr[0]<0) max = 0 ;
     else max = arr[0] ;

     for (m[0]=arr[0], j=1; j<len; j++) {
          m[j] = dp_max(m[j-1]+arr[j], arr[j]) ;
          if (m[j]>=max) {
               max = m[j] ;
               e = j ;
               if (m[j] == arr[j])
                    s = j ;
          }
     }

     printf("\n\nMax Contiguous Sequence starts@ %d and ends@ %d and sums to %d\n", s, e, max) ;

     return max ;
}

int main()
{
     int i, arr[MAX_N] ;

     #ifndef ONLINE_JUDGE
     freopen("dp_max_contiguous_subseq.in", "r", stdin) ;
     #endif

     i = 0 ;
     while (scanf("%d", &arr[i]) != EOF) i++ ;
     dp_max_contiguous_subseq(arr, i) ;

     return 0;
}

Useful Bit-manipulation Functions

/* Function to print binary representation of a number */
void printBinary(int n)
{
     int i ;
     for (i=31; i>=0; i--)
          printf("%d", ((1<<i & n))?1:0) ;
     printf("\n") ;
}

/* Function to get 2's complement of a number */
int get2scomplement(int n)
{
     int i, k=0 ;
     for (i=0; i<32; i++)
          k |= ~(1<<i | n) ;
     k+=1 ;

     return k ;
}