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

int FindSortedArrayRotationRecursive(int *array, int start, int end)
{
	if(start == (end-1))
		return start+1;
	if(array[start] <= array[end-1])
		return 0;
	int middle = (start + end)/2;
	if(array[start] > array[middle])
		return FindSortedArrayRotationRecursive(array, start, middle);
	else
		return FindSortedArrayRotationRecursive(array, middle, end);
}

int FindSortedArrayRotationIterative(int *array, int length)
{
    int start = 0;
	int end = length-1;
	if(array[start] < array [end])
		return start;	
	while(start != end)
	{
		int middle = (start+end)/2;
		if(array[start] < array[middle])
			start = middle;
		else
			end = middle;
	}
	return start+1;
}

int main()
{
    int array[] = { 8, 9, 10, 1, 2, 3, 4, 5, 6, 7};
    int x = FindSortedArrayRotationRecursive(array, 0, 10);
    int y = FindSortedArrayRotationIterative(array, 10);
    printf("%d\n", x);
    printf("%d\n", y);
}

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

int isPalindrome(char *word)
{
	if(NULL == word)
		return 0;
	int length = strlen(word);
	if(1 == length || 0 == length)
		return 1;
	int start = 0;
	while(word[start] == ' ')
		start++;
	int end = length - 1;
	while(word[end] == ' ')
		end--;
	for(int i = start, j = end; i<=j; i++, j--)
	{
		if(word[i] == ' ' || word[j] == ' ')
			return 0;
		if(word[i] != word[j])
			return 0;
	}
	return 1;
}

int main()
{
	printf("%d\n", isPalindrome(NULL));
	printf("%d\n", isPalindrome(""));
	printf("%d\n", isPalindrome("a"));
	printf("%d\n", isPalindrome("adadasfdf"));
	printf("%d\n", isPalindrome("abba"));
	printf("%d\n", isPalindrome("aba"));
	printf("%d\n", isPalindrome("       abba"));
	printf("%d\n", isPalindrome("    abba    "));
	printf("%d\n", isPalindrome("ab    ba"));
	return 0;
}

#include<stdio.h>
#define NONE -1
#define EQUILATERAL 0
#define ISOSCELES 1
#define SCALENE 3

int isTriangle(int a, int b, int c)
{
	if(a < 1 || b < 1 || c < 1)
		return NONE;
	if(a+b <= c || a+c <= b || c+b <= a)
		return NONE;
	if(a == b && a == c)
		return EQUILATERAL;
	if(a == b || b == c || a == c)
		return ISOSCELES;
	else
		return SCALENE;
}

int main()
{
	printf("%d\n", isTriangle(11,10,17));
	printf("%d\n", isTriangle(11,10,11));
	printf("%d\n", isTriangle(11,11,11));
	printf("%d\n", isTriangle(11,110,11));
	printf("%d\n", isTriangle(11,0,11));
	return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NHASH 29989 //Use a prime number!
#define MULT 31

struct node
{
	char *word;
	int count;
	struct node * next;
} node;

typedef struct node Node;

Node *bin[NHASH];

unsigned int hash(char *p)
{
	unsigned int h = 0;
	for(; *p; p++)
		h = MULT * h + *p;
	return h % NHASH;
}

void incword(char *s)
{
	Node * p;
	int h = hash(s);
	for(p = bin[h]; p!= NULL; p = p->next)
	{
		if(strcmp(s, p->word) == 0)
		{
			(p->count)++;
			return;
		}
	}
	p = (Node *)malloc(sizeof(node));
	if(!p)
		return;
	p->count = 1;
	p->word = (char *)malloc(strlen(s)+1);
	strcpy(p->word, s);
	p->next = bin[h];
	bin[h] = p;
}

int main()
{
	char buf[100];
	for (int i=0; i<NHASH; i++)
		bin[i] = NULL;
	while(scanf("%s", buf) == 1)
		incword(buf);
	for (int i = 0; i < NHASH; i++)
		for (Node * p = bin[i]; p != NULL; p = p->next)
			printf("%s %d\n", p->word, p->count);
	return 0;
}

void print_help()
{
        printf("usage:\n") ;
        printf("\t\t-i set input file\n") ;
        printf("\t\t-o set output file\n") ;
        printf("\t\t-c set config file\n") ;
        printf("\t\t-h print this help information\n") ;
        printf("\t\t-v print version\n") ;
}
 char* input_file = NULL ;
        char *query=NULL;
          char opt_char=0;
        while ((opt_char = getopt(argc, argv, "i:q:vh")) != -1)
        {
                switch(opt_char)
                {
                        case 'h':
                                print_help();
                                exit(-1);
                                break;
                        case 'v':
                                print_version() ;
                                exit(-1) ;
                                break ;
                        case 'i':
                                input_file= optarg ;
                                break ;
                        case 'q':
                                query= optarg ;
                                break ;
                        default:
                                print_help();
                                exit(-1);
                                break;
                }
        }

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

char* deleteCharacters(char * str, char * charSet)
{
	int hash [256];
	if(NULL == charSet)
		return str;
	for(int i = 0; i < 256; i++)
		hash[i] = 0;
	for(int i = 0; i < strlen(charSet); i++)
		hash[charSet[i]] = 1;
	int currentIndex = 0;
	for(int i = 0; i < strlen(str); i++)
	{
		if(!hash[str[i]])
			str[currentIndex++] = str[i];
	}
	str[currentIndex] = '\0';
	return str;
}

int main()
{
    char s[2] = "a";
    char s2[5] = "aca";
	printf("%s", deleteCharacters(s2, s));
	return 0;
}

#include<stdio.h>
#define MAX 200
/*
	F0 = 1.
	F1 = 1.
	Fn = Fn-1 + Fn-2 
*/

int fibonacciRecursive(int n)
{
	if(n == 0)
		return 0;
	if(n == 1)
		return 1;
	else
		return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
}

int fibonacciIterative(int n)
{
	int a = 0;
	int b = 1;
	int fib;
	if(n == 0)
		return a;
	if(n == 1)
		return b;
	for(int i = 2; i <= n; i++)
	{
		fib = a + b;
		a = b;
		b = fib;
	}
	return fib;
}

int fibonaccis[MAX];


int fibonacciMemoization(int n)
{
	if(n == 0)
		return 0;
	if(n == 1)
		return 1;
	if(fibonaccis[n])
		return fibonaccis[n];
	else
	{
		fibonaccis[n] = fibonacciMemoization(n-1)+ fibonacciMemoization(n-2);
		return fibonaccis[n];
	}
}

int main()
{
	for(int i = 0; i < MAX; i++)
		fibonaccis[i] = 0;
	printf("Fibonacci %d = %d\n", 0, fibonacciMemoization(0));
	printf("Fibonacci %d = %d\n", 2, fibonacciMemoization(2));
	printf("Fibonacci %d = %d\n", 3, fibonacciMemoization(3));
	printf("Fibonacci %d = %d\n", 4, fibonacciMemoization(4));
	printf("Fibonacci %d = %d\n", 5, fibonacciMemoization(5));
	printf("Fibonacci %d = %d\n", 6, fibonacciMemoization(6));
	printf("Fibonacci %d = %d\n", 7, fibonacciMemoization(7));
	printf("Fibonacci %d = %d\n", 8, fibonacciMemoization(8));
	printf("Fibonacci %d = %d\n", 13, fibonacciMemoization(13));
	printf("Fibonacci %d = %d\n", 16, fibonacciMemoization(16));
	printf("Fibonacci %d = %d\n", 19, fibonacciMemoization(19));
	printf("Fibonacci %d = %d\n", 20, fibonacciMemoization(20));
	printf("Fibonacci %d = %d\n", 20, fibonacciMemoization(40));
	return 0;
}

/*
	F0 = 0
	F2 = 1
	F8 = 21
	F13 = 233
	F16 = 987
	F19 = 4181
	F20 = 6765
*/

#include<stdio.h>
#include<math.h>
#define MAX 1000


int prime[MAX];

int isPrimeNaive(int n)
{
	if(n <= 1)
		return 0;
	for(int i = 2; i < n; i++)
		if(n % i == 0)
			return 0;
	return 1;
}

int isPrime(int n)
{
	if(n<= 1)
		return 0;
	if(n == 2)
		return 1;
	if(n%2 == 0)
		return 0;
	int limit = (int)sqrt((double)n);
	for(int i = 3; i <= limit; i=i+2)
	{
		if(n % i == 0)
			return 0;
	}
	return 1;
}

void sieve()
{
	prime[0] = 0;
	prime[1] = 0;
	for(int i = 2; i < MAX; i++)
		prime[i] = 1;
	int limit = (int)sqrt((double)MAX);
	for(int i = 2; i <= limit; i++)
	{
		if(prime[i])
			for(int j = i*i; j <= MAX; j+=i)
				prime[j] = 0;
	}
}

int isPrimeSieve(int n)
{
	if(prime[n])
		return 1;
	else
		return 0;
}

int main()
{
	sieve();
	printf("N=%d %d\n", 1, isPrime(1));
	printf("N=%d %d\n", 2, isPrime(2));
	printf("N=%d %d\n", 3, isPrime(3));
	printf("N=%d %d\n", 4, isPrime(4));
	printf("N=%d %d\n", 7, isPrime(7));
	printf("N=%d %d\n", 9, isPrime(9));
	printf("N=%d %d\n", 13, isPrime(13));
	printf("N=%d %d\n", 17, isPrime(17));
	printf("N=%d %d\n", 100, isPrime(100));
	printf("N=%d %d\n", 23, isPrime(23));
	printf("N=%d %d\n", 1, isPrime(1));
	return 0;
}