Given an array of integers and another integer X - create an algorithm to determine if the sum of any two integers in the array would result in x. I was asked to use hash tables for this. The solution is create a hash table with the array of integers and set the data to one. Access the hash table with keyvalue x-arr[i] and check if data is set, if yes then count. Any suggestions what should be the hash function to retrieve the data in constant time??
A:
This sounds much like the knapsack problem Only you're constrained to exactly two values to sum.
For your hash function, since you're dealing with simple integers, it is tolerable to do a modulo with a number that is mutually prime with the length of the hashmap. So if your using 10 buckets, 7 or 9 would work, but generally a prime number is good. Check out this page and hash functions for finer details.
JoshD
2010-09-29 03:20:04