TITLE:-Pair sum in array
PROBLEM:-
Given a random integer array A and a number x. Find and print the pair of elements in the array which sum to x.
Array A can contain duplicate elements.
While printing a pair, print the smaller element first.
That is, if a valid pair is (6, 5) print “5 6”. There is no constraint that out of 5 pairs which have to be printed in 1st line. You can print pairs in any order, just be careful about the order of elements in a pair.
Line 1 : Integer N (Array size)
Line 2 : Array elements (separated by space)
Line 3 : Integer x
Line 1 : Pair 1 elements (separated by space)
Line 2 : Pair 2 elements (separated by space)
Line 3 : and so on
Constraints :
1 <= N <= 1000
1 <= x <= 100
9
1 3 6 2 5 4 3 2 4
7
Sample Output :
1 6
3 4
3 4
2 5
2 5
3 4
3 4
SOLUTION:-
#include<iostream>
using namespace std;
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
//marge temp arrays to real array
while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i];
i++; k++;
}
while(j<nr) { //extra element in right array
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
void pairSum(int input[], int size, int x) {
mergeSort(input,0,size-1);
int i=0,j=size-1,counti=1,countj=1,elei,elej;
while(i<j)
{
if(input[i]+input[j]==x)
{
while(input[i]==input[i+1])
{
counti++;
i++;
}
if(input[i]==input[j]){
int a=(counti-1)*(counti)/2;
for(int p=0;p<a;p++){
cout<<input[i]<<' '<<input[i]<<endl;
}
i++;
j--;
counti=1;
countj=1;
}
else {
while((input[j]==input[j-1]))
{
countj++;
j--;
}
for(int p=0;p<counti*countj;p++)
cout<<input[i]<<' '<<input[j]<<endl;
i++;
j--;
counti=1,countj=1;
}
}
else if(input[i]+input[j]>x)
{
j--;
}
else
i++;
}
}
int main() {
int size;
int x;
cin>>size;
int *input=new int[1+size];
for(int i=0;i<size;i++)
cin>>input[i];
cin>>x;
pairSum(input,size,x);
return 0;
}