Saturday, January 21, 2012

Find all the pairs in an array of integers which sum X (in C)

/*
* main.c
*
* Created on: Jan 21, 2012
* Author: julio
*/
#include

void findPairsAdding(int array[], int size, int sum){

// Assuming the array is sorted
int i = 0, j = size -1;
while(i < j){
if(array[i] + array[j] == sum){
// We have found a pair, now let's take care of duplicates
int k = i, l = j;
// From i to k duplicated values of the lower value
while(k < l && array[k] == array[k +1])
k++;
// from k to l duplicated values of the higher value
while(k < l && array[l] == array[l -1])
l--;
int aux1 = i, aux2 = j;
for(aux1 = i ; aux1 <= k ; aux1++){
for(aux2 = j; aux2>=l; aux2--){
printf("i: %d, j: %d, (%d, %d) = %d\n",aux1,aux2,
array[aux1],array[aux2],sum);
}
}
i = aux1-1;
j = aux2+1;
}
if(array[i] + array[j] > sum)j--;
else i++;
}
}

int main(int argc, char ** argv){
int a[] = {1,2,8,9};
findPairsAdding(a,4,10);
return 0;
}