Saturday, October 31, 2015

Given an array A[] and a number x, check for pair in A[] with sum as x

/* Given an array A[] and a number x, check for pair in A[] with sum as x */

#include <stdio.h>
void quickSort(int*, int, int);
void printSumPair(int A[], int arr_size, int sum) {
    int l, r;
    // sort in increasing order
    quickSort(A, 0, arr_size - 1);
    l = 0;
    r = arr_size-1;
    while (l < r) {
        if (A[l] + A[r] > sum)
            r --;
        else if (A[l] + A[r] < sum)
            l++;
        else {
            printf("%d + %d equals %d\n", A[l], A[r], sum);
            break;
        }
    }
}

int main() {
    int arr[] = {1,4,45,6,10,8};  // sorted would be : {1,4,6,8,10,45}
    int x = 16;
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printSumPair(arr, arr_size, x);
    return 0;
}

void exchange (int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition (int A[], int si, int ei ) {
    int x  = A[ei];
    int i = si - 1;
    int j;
    for (j = si; j <= ei - 1; j++) {
       if(A[j] <= x) {
         i++;
         exchange (&A[j], &A[i]);
       }
    }
    exchange (&A[i+1], &A[ei]);
    return (i+1);
}

void quickSort (int A[], int si, int ei) {
    int pi;
    if (si < ei ) {
       pi = partition(A, si, ei);
       quickSort(A, si, pi-1);
       quickSort(A, pi+1, ei);
    }
}

No comments:

Post a Comment