Find pair of numbers in array that add to given sum :
Complexity: O(n logn)
Approach :
step 1: Sort an array using efficient sorting method
step 2: use two variable i & j , initialize i as starting position of array (i=0) and j as last position of array (j=n-1). Where n is number of element in array.
step 3: if(A[i]+A[j]<x) i++
else if(A[i]+A[j]>x) j–
else (A[i]+A[j]==x) print A[i] , A[j] and i++
step 4: Repeat step 3 untill i<j
Code to Find pair of numbers in array that add to given sum :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<stdio.h> void swap(int *p,int *q){ int t; t=*q; *q=*p; *p=t; } int partition(int [],int ,int); void quicksort(int A[],int p,int r){ int q; if(p<r){ q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } int partition(int A[],int p,int r){ int x,i,j; x=A[r]; i=p-1; for(j=p;j<r;j++){ if(A[j]<=x){ i=i+1; swap(&A[i],&A[j]); } } swap(&A[i+1],&A[r]); return i+1; } void sum_of_pair_as_x(int A[],int n,int x){ int i=0,j=n-1; while(j>i){ if(A[i]+A[j]<x) i++; else if(A[i]+A[j]>x) j--; else {printf(" [ %d ,%d ] ",A[i],A[j]); i++;} } } void print_array(int A[],int n){ int i=0; for(i=0;i<n;i++) printf(" %d ",A[i]); printf("\n"); } int main() { int Arr[]={7,8,3,1,2,4,6,5}; int x=9; int n=sizeof(Arr)/sizeof(Arr[0]); quicksort(Arr,0,n-1); printf("\n Pair of sum %d are : \n",x); sum_of_pair_as_x(Arr,n,x); printf("\n"); return 0; } |