CareerCup

the second function signature is equivalent to the first one and you still need a size parameter.

i don't think i understand your solution. first of all, we are only comparing to one sum element (function parameter), therefore hashing is not necessary - it's a straight compare.
second, you need to go through all possible pair combinations, which means you will have two, nested loops - running time O(n^2).

bool pairExist(int * arr, int size, int sum)
{
for(int i = 0; i < size; ++i)
{
for(int j = i + 1; j < size; ++j)
{
if(sum == (arr[i] + arr[j]))
{
return true;
}
}
}
return false;
}

The second one is different. Since we can figure out size by sizeof(arr)/sizeof(int) to figure out the size of array.

Using hash is to sacrifice some space to reduce time complexity. Brute force, it is O(n^2). Using hash, it use O(n) space but O(n) time.

You were right about the function signature - thanks for the correction.

I see your logic, but what about the following case:

sum = 10
arr = { 1, 2, 4, 5 };
hashset = { 9, 8, 6, 5 };

Your algorithm would return a false positive. It would have to handle a special case of 0.5 * sum differently.

Right. So we could also keep a position in the hash. And we only match when the positions are different.

Sorting once seems like it is the solution to many of these type of questions. Then, like mentioned, a binary search for the required difference, or, what first came to me, just stopping the list traversal when the sum is greater than 'sum', since all further results will be greater. There is probably some hybrid with a hash that would reduce clock cycles/runtime further.

Of course, I could be wrong since I devoted more time typing this, than I did on the solution.