#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NODE_SIZE sizeof(struct node)

/*
 *	Eingabe bitte per stdin, etwa
 *		./a.out < test.txt
 *	in einem Linux-System. Die Inputdatei muss das
 *	folgende Format haben:
 *		<Anzahl der Listenelemente n> <e_1> ... <e_n>
 */

struct node {
	struct node* next;
	int element;
};

int hash( int x, int m, int c );
int has_doublet( int n, int* list );
int counter = 0;

int main( char** args ) {
	srand(time(NULL));

	int n, res;
	res = scanf("%d", &n );
	if ( res < 1 ) {
		printf("Keine Eingabe auf stdin");
		return -1;
	}

	printf("Lese Liste mit %d Elementen\n", n );

	int* list = malloc(n*sizeof(int));
	for( int i = 0; i < n; i++ ) {
		res = scanf("%d", &list[i] );
		if ( res < 1 ) 
			return -1;
	}

	printf("Suche nach Duplikaten\n" );
	
 	res = has_doublet( n, list );

	if ( res == TRUE )
		printf("Liste enhält Duplikate\n");
	else
		printf("Liste enthält keine Duplikate\n");


	printf("Operationen: %i \n", counter );

	free( list );
	return 0;
}

int hash( int x, int m, int c ) {
	int r = x % 23;
	r *= r;
	r *= r;
	return ((x%m)*(x%m) + 3*x + r + c) % m;
}

int has_doublet( int n, int* list ) {
	int m = 2*n;
	int c = rand()%1000;
	struct node** buckets = malloc(m*NODE_SIZE);

	for( int i = 0; i < m; ++i )
		buckets[i] = NULL;
	
	for( int i = 0; i < n; ++i ) {
		if ( list[i] < 0 ) return 0;

		int key = hash( list[i], m, c );
		if ( key < 0 ) {
			// Integer-overflow
			return FALSE;
		}

		struct node* current = buckets[key];
		++counter;
		if ( current == NULL ) {
			buckets[key] = current = malloc(NODE_SIZE);
		} else {
			while(++counter) {
				if ( current->element == list[i] )
					return TRUE;

				if ( current->next == NULL )
					break;

				current = current->next;
			}

			current->next = malloc(NODE_SIZE);
			current = current->next;
		}
		
		current->next = NULL;
		current->element = list[i];
	}	

	return FALSE;
}