Find pairs of numbers of numbers in an array with all pairs giving the same sum

Question

Suppose there is an array of size N (N is always even). Given all the elements of the array form a pair,which gives the same sum when added. Find the sum. This is definitely not homework. For example :

A = {1,4,3,2,5,6,8,7} . ans = 9 because { (1,8) , (2,7) , (3,6) , (4,5) } form pairs of sum 9.

There can be duplicates also. B = {3,4,5,3,4,5}. ans = 8

What I have tried is

1) Sort the array = O(nlogn).

2) find the sum of min and max of the sorted array. This is the sum required because if it is anything other than these 2, there will be at least one pair which cant be formed with the same sum. Hope I am clear.

Now my question, can this be done in linear time somehow? Hashing the numbers directly wouldn't suffice because the "Sum" is not known beforehand.

Answer 1

Make an O(n)-time pass through the set of numbers to find the min and max and to put all the numbers into a hash-table. Compute the target sum t = max + min. Then make a second O(n)-time pass through the set of numbers; for the number x, compute y = t-x, look for y in the hash table, and if it's found, report the pair. Regarding duplications, you also could keep counts of numbers in the hash table.

Answer 2

Find the sum of the array, double it, and divide by N.