CareerCup

You should add all elements of array to HashMap. When you add number e, find if number (n - e) already presents in HashMap. But be careful with value n/2, if n is even.

You can consider this approach in O(n):
a. Make an array say of 1000 integers and all intialized to 0.
b. Take a temp variable and calculate the difference of the sum and the array and set the occurence of that particular integer to 1 by indexing that integer in the array of 1000 integers.
c. If the temp>=0 and if the array is set for that number then print the pair.
d. It prints all the valid pairs.

#include <stdio.h>
#include <conio.h>

void findSumPair(int arr[],int n,int sum)
{
	int bin[1000]={0},i,temp;
	for(i=0;i<n;i++)
	{
		temp=sum-arr[i];
		if(temp>=0&&bin[temp]==1)
		{
			printf(" %d %d ",temp,arr[i]);
		}
		bin[arr[i]]=1;
	}
}
int main()
{
	int arr[]={2,1,3,4,6,5,7,8,21,9};
	int n=sizeof(arr)/sizeof(arr[0]);
	findSumPair(arr,n,7);
}

public static void enumrate(int [] array, int target){
		
		HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
		
		for (int i=0;i<array.length;++i){
			if (map.containsKey(array[i])){
				System.out.println(array[i] + " " + map.get(array[i]));
			}else{
				int difference=target-array[i];
				map.put(difference, array[i]);
			}
		}

}

void FindPairs(int[] arr, int n, int sum)
{
	sort(arr); //assuming there's a sorting method
	int index_a = 0;
	int index_b = n-1;
	while (arr[index_a] < arr[index_b])
	{
		if (arr[index_a] + arr[index_b] > sum)	
		{
			index_b++;
		}
		else if (arr[index_a] + arr[index_b] < sum)
		{
			index_a++;
		}
		else
		{
			printf ("%d, %d \n", arr[index_a], arr[index_b]);
			index_a++;
			index_b++;
		}
	}
}

Use a hash table, and hash all number in one go...this takes n*o(1) = o(n) time
Next make another pass on the numbers, this time check if sum - array[i] exists, if it does print the pair...this takes o(n) time...
Therefore total time is o(n)

In Javascript:

function pairsWithSum(sum, array){
	var i, rest, currentVal;
	var table = {};
	var result = [];

	for(i=0; i< array.length;i++){
		currentVal = array[i];
		rest = sum - currentVal;
		table[currentVal] = true;
		if(table[rest]){
			result.push([currentVal, rest]);
		}
	}
	return result;
}

1. Arrange the array in ascending order.

2. No take the first element in sorted array, substract given sum with the first element and try to find the difference in the remaining array using binary search (complexity log n). If the other number of the pair is preasent the remove both element and add it to your answer. If no matching pair is found then remove the element for which the matching pair was not found. This will reduce the size of the array for further calculation.
3. Carry on above steps till all posible pair are traversed.