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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| #include <iostream>
using namespace std;
struct pairSum{
int sum, first, second;
};
void findPairSum(int *arr, struct pairSum *temp, int n){
int k = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
temp[k].sum = arr[i] + arr[j];
temp[k].first = arr[i];
temp[k].second = arr[j];
k++;
}
}
}
void merger(struct pairSum *arr, struct pairSum *temp, int low, int mid, int high){
int i = low, j = mid + 1, k = low;
while(i <= mid && j <= high){
if(arr[i].sum <= arr[j].sum){
temp[k].sum = arr[i].sum;
temp[k].first = arr[i].first;
temp[k].second = arr[i].second;
k++;
i++;
} else{
temp[k].sum = arr[j].sum;
temp[k].first = arr[j].first;
temp[k].second = arr[j].second;
k++;
j++;
}
}
while(i <= mid){
temp[k].sum = arr[i].sum;
temp[k].first = arr[i].first;
temp[k].second = arr[i].second;
k++;
i++;
}
while(j <= high){
temp[k].sum = arr[j].sum;
temp[k].first = arr[j].first;
temp[k].second = arr[j].second;
k++;
j++;
}
for(int i = low; i<= high; i++){
arr[i].sum = temp[i].sum;
arr[i].first = temp[i].first;
arr[i].second = temp[i].second;
}
}
void mergeSort(struct pairSum *arr, struct pairSum *temp, int low, int high){
if(low < high){
int mid = (low + high) / 2;
mergeSort(arr, temp, low, mid);
mergeSort(arr, temp, mid + 1, high);
merger(arr, temp, low, mid, high);
}
}
void find4Numbers(struct pairSum *arr, int sz, int x){
struct pairSum *sorted = new pairSum[sz];
int l = 0, r = sz - 1, sum;
mergeSort(arr, sorted, 0, sz - 1);
while(l < r){
sum = sorted[l].sum + sorted[r].sum;
if(sum == x && (sorted[l].first != sorted[r].first && sorted[l].first != sorted[r].second
&& sorted[l].second != sorted[r].first && sorted[l].second != sorted[r].second)){
cout << "Four elements : " << sorted[l].first << ", " << sorted[l].second << ", " << sorted[r].first << ", " << sorted[r].second << endl;
return;
} else if(sum > x){
r--;
} else{
l++;
}
}
cout << "No 4 elements found!" << endl;
return;
}
int main(){
int arr[] = {1, 4, 45, 6, 10, 12};
int x = 56;
int n = sizeof(arr)/sizeof(arr[0]);
int sz = n * (n - 1) / 2;
struct pairSum *pairSums = new struct pairSum[sz];
findPairSum(arr, pairSums, n);
find4Numbers(pairSums, sz, x);
return 0;
}
|
