Question: Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target If pre-processing of source in the above is allowed, what pre-processing will you do to reduce the complexity of algorithm written above ?


Solution: 1) Initialize Binary Hash Map M[] = {0, 0, …}
2) Do following for each element A[i] in A[]
(a) If M[x - A[i]] is set then print the pair (A[i], x – A[i])
(b) Set M[A[i]]
#include
#define MAX 100000

void printPairs(int arr[], int arr_size, int sum)
{
int i, temp;
bool binMap[MAX] = {0}; /*initialize hash map as 0*/

for(i = 0; i < arr_size; i++)
{
temp = sum - arr[i];
if(temp >= 0 && binMap[temp] == 1)
{
printf("Pair with given sum %d is (%d, %d) \n", sum, arr[i], temp);
}
binMap[arr[i]] = 1;
}
}

/* Driver program to test above function */
int main()
{
int A[] = {1, 4, 45, 6, 10, 8};
int n = 16;
int arr_size = 6;

printPairs(A, arr_size, n);

getchar();
return 0;
}
Works in O(n)