#include <stdbool.h>
#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)
bool twoSum(int arr[], int size, int sum) {
	for (int i = 0; i < size; i++) {
		for (int j = i + 1; j < size; j++) {
			if (arr[i] + arr[j] == sum) {
				return true;
			}
		}
	}

	return false;
}
#endif

#if 1
// Our second solution
bool twoSum(int arr[], int size, int sum) {
	// For each element x of the array, check if (sum - x) is
	// in the hash table, then insert x into the hash table
	
	HashTable ht = HashTableNew();

	for (int i = 0; i < size; i++) {
		if (HashTableContains(ht, sum - arr[i])) {
			HashTableFree(ht);
			return true;
		}
		HashTableInsert(ht, arr[i], 0);
	}

	HashTableFree(ht);
	return false;
}
#endif