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

#include "HashTable.h"

// NOTE: To enable/disable a solution, change the #if 0 to #if 1
//       (or vice versa). Only one solution should be enabled at
//       a time.

#if 0
// Our first solution (inefficient)
int oddOccurring(int arr[], int size) {
	int numOddOccurring = 0;
	HashTable ht = HashTableNew();

	for (int i = 0; i < size; i++) {
		int count = 0;
		for (int j = 0; j < size; j++) {
			if (arr[j] == arr[i]) {
				count++;
			}
		}

		if (count % 2 == 1 && !HashTableContains(ht, arr[i])) {
			numOddOccurring++;
			HashTableInsert(ht, arr[i], 0);
		}
	}

	HashTableFree(ht);
	return numOddOccurring;
}
#endif

#if 0
// Our second solution
int oddOccurring(int arr[], int size) {
	HashTable ht = HashTableNew();

	for (int i = 0; i < size; i++) {
		int count = HashTableGetOrDefault(ht, arr[i], 0);
		HashTableInsert(ht, arr[i], count + 1);
	}

	int numOddOccurring = 0;
	for (int i = 0; i < size; i++) {
		int count = HashTableGetOrDefault(ht, arr[i], 0);
		if (count % 2 == 1) {
			numOddOccurring++;
			HashTableDelete(ht, arr[i]);
		}
	}

	HashTableFree(ht);
	return numOddOccurring;
}
#endif

#if 1
// Our third solution
int oddOccurring(int arr[], int size) {
	HashTable ht = HashTableNew();

	for (int i = 0; i < size; i++) {
		if (HashTableContains(ht, arr[i])) {
			HashTableDelete(ht, arr[i]);
		} else {
			HashTableInsert(ht, arr[i], 0);
		}
	}

	int count = HashTableSize(ht);
	HashTableFree(ht);
	return count;
}
#endif