CareerCup

see the introduction to algorithms by carman book O(nlogn) is complexcity...

integer pairs?? does that mean 2 numbers at a time..?? 2 consecutive numbers or just any 2 numbers in the whole array?

sol1 - use hash table - add element in an array then check the diff (m - new element) in hash table.

sol 2 sort an array - pick element from start and end, check if sum is equal to m if not then sum > m then pick next element from last if sum < m, select next element from start

sorting cannot be considered for this as sorting itself takes O(nlogn).
we can consider the hash table approach and in that case run time would be O(n), Is that acceptable @ gs2005?

can some one pls explain the hash approach more clearly .. "add element in an array then check the diff (m - new element) in hash table.
"

He is saying:
-Insert all elements in array into hash table.
-While not end of array
{
Get next element, x, from array.
Look up m-x in hash table, if found break out of loop
}

We can use "Counting sort" here (runs in O(n)), because the range is known (range = sum). But the range should be reasonably small.

int [] hashArr = {1,3,7,12,2,71,8,9,10,6,4};
int numEle = hashArr.length;
Hashtable ht = new Hashtable();
// Add all the elements to the Hash Table
for(int i=0;i<numEle;i++)
ht.put(i, hashArr[i]);
// Check the difference, sum - i = ex whether in HashTable
int sum = 10;
int diff = 0;
for(int j=0;j<numEle;j++){
diff = sum-hashArr[j];
if(ht.contains(diff))
System.out.println(hashArr[j]+":"+diff);
}

gs2005: what was your answer, as all of us are trying to make use of hash to get a O(n) solution. do you have any good answer, at least better than our approach.

What if the sum is 50.. and the array contents are {25,45,30}... ? First it selects 25 and again searching in hash returns 25.. a pair(25,25) that does not exist..