CareerCup

Sort the elements of the array using merge sort technique.
This operation takes O(nlogn) time.
Now let's say "i" is the first index of the array and "j" is the last index of the array. use the following algorithm.
while(i < j)
{
  if((arr[i] + arr[j]) == key)
  {
     printf("(%d,%d)",arr[i],arr[j]);
     i++;
     j++;
  }
  else((arr[i] + arr[j]) > key)
  {
    j--;
  }
  else
  {
    i++;
  }
}

This operation takes O(n) time.
So, overall complexity of the algorithm is O(nlogn).

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(a[i]+a[j]==X&&i!=j)
print (i,j);
}}

Using a hash_map. complexity depends on hash function but in general recent hash functions give a amortized O(1) insertion and amortized O(1) retrieval.

Assuming the values in the hash_map are all positive.
-> For every value 'val' in the array, 
   if sum-val >=0
       if sum-val exists in the hash_map, add to the matching pairs vector.
       else insert 'val' in the hash_map
-> print all elements of the matching pairs vector.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using std::cout;using std::vector;using std::endl;
typedef int DataType;
typedef std::unordered_map<DataType, int> MyHashMap;
void printVecPair (vector<DataType> v) {
  cout << v[0]<<" : "<<v[1]<<endl;
}
int main(){ 
	MyHashMap valsMap; 			//declare unordered map
	vector<DataType> array {12,20,13,4,1,2,8,6,7,7,3,5,9};
	DataType sum=14,val=0;
	vector<vector<DataType> > matches;	//vector to store pairs of values whose sum = sum
	DataType len = array.size();
	vector<DataType>::const_iterator arrItr;
	MyHashMap::iterator mapItr = valsMap.begin();
	//for every val in the array if (sum-val) >0 see if there exists a value (sum-val)
	for ( arrItr=array.begin(); arrItr!=array.end(); arrItr++ ){
		val = *arrItr;
		if((sum-val)<0)
			continue;
		mapItr = valsMap.find((sum-val));
		if(mapItr==valsMap.end()){	//if sum-val not found then insert
			valsMap.insert(MyHashMap::value_type(val, 1));
		}else				//else add it to the matches vector
			matches.push_back(vector<DataType>{val,(sum-val)});
	}
	cout<<"value pairs whose sum = "<<sum<<endl;
	for_each (matches.begin(),matches.end(),printVecPair);
}

Let me know if there are any bugs. Thanks

1. A[n] array and SUM .Take temp array B[n]

2. for each i=0 to n-1
if A[i] > SUM/2
B[i] = SUM - A[i]
else
B[i] = A[i]
3. Now B[n] array contains elements <= SUM/2 .
4. if B[n] contains duplicate element, then B[i] and SUM-B[i] elements gives SUM of two elements.
else
A[n] does not contains two such numbers to give SUM.
5. Time complexity o(n) & Space complexity O(n)
6. The above logic is Problem reducing i.e finding Two numbers sum problem to duplicate problem

logic is same as above guys and this code will handle even negative nos.
O(n) time and space.

#include<stdio.h>

void pair(int a[], int l, int sum)
{
int i, j, min;

if(l<2)
{
printf("no pair");
return ;
}
min = a[0];
for( i = 1 ;i<l;i++)
{
if(min > a[i] )
min = a[i];
}

if(min<0)
{
min*= -1;
sum += min;
sum += min;
for( i = 0 ;i<l;i++)
     a[i] += min;
}
else
min = 0;
int hash[sum];
for( i = 0 ;i<sum;i++)
{
hash[i] = sum+1;

}
for( i = 0 ;i<l;i++)
{

   if(sum >= a[i] )
{
      if (hash[a[i]] == sum+1)
      {
       hash[sum-a[i]] = 0;
      }
 else if(hash[a[i]] == 0)
 {
 printf("\npair found{%d, %d}.\n", a[i]- min, sum-a[i]-min);
 }
}
}
}
int main()
{
int a[] = {5,2,1,4,6,12,2,3};
pair(a, 8, 3);
return 0;

}

def fun(X):
        uniquePairDict = {}
        for element in arr:
            rest = X - element
            if rest in arr:
               pairString = "(" + element + "," + rest + ")"
               if pairString not in uniquePairDict:
                  uniquePairDict[pairString] = 0
         print uniquePairDict