CareerCup

Why hashing method can not handle negative numbers?

Step 1: Sort --> O(nlogn)

Step 2: assuming A is array of size n,
let i=0 and j=n-1
if A[i]+A[j] > x then j--
else if A[i]+A[j] < x then i++
if equal then return i,j
repeat this till i<j --> O(n)

total complexity: O(nlogn)

Can someone explain this ? How this works ?
>>>> 2. Uisng sorting as a preprocessing step and binary search. ie. O(nlogn).

It should be able to handle negative numbers just fine.
Some pseudocode..

Let the number we're trying to sum upto be SUM

Step 1.
foreach(int n in array)
{
	int complement = SUM - n;
	if(hashTable.containsKey(complement)
		return true; // found the pair {n, complement}

	hashTable.Add(n, complement); 

// You can simply choose to add true or 1 here. I chose to add the complement value as the
// value part of the key,value pair thing.
}

Step2. There is no step 2.

It should work wiht -ve numbers just fine

for example

a  = [2, -2, 5, 6, 9, -14, -3]
sum = 3

hashtable[-2] = 5
so -2, and 5 will be a valid pair