इस समस्या में, हमें 3 सरणी X, Y, Z दिए गए हैं। हमारा कार्य 3 सरणियों से तत्वों वाले विशेष ट्रिपल के योग को खोजने के लिए एक प्रोग्राम बनाना है।
विशेष ट्रिपल एक विशेष प्रकार का त्रिक है जिसमें निम्नलिखित गुण होते हैं -
के लिए (ए, बी, सी):ए ≤ बी और बी ≥ सी, यानी त्रिक का मध्य तत्व अन्य दो से अभिवादन करने वाला होना चाहिए।
और, त्रिक का मान सूत्र द्वारा दिया जाता है -
f(a, b, c) = (a+b) * (b+c)
इस ट्रिपलेट को बनाने के लिए हमें दिए गए तीन सरणियों के एक दूसरे से एक तत्व का उपयोग करने की आवश्यकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट -
X[] = {5, 9, 4} ; Y[] = {8, 6} ; Z[] = {7, 1} आउटपुट
स्पष्टीकरण − आइए सभी विशेष त्रिक के मान ज्ञात करें।
(5, 8, 7) : value = (5+8) * (8+7) = 195 (5, 8, 1) : value = (5+8) * (8+1) = 117 (4, 8, 7) : value = (4+8) * (8+7) = 180 (4, 8, 1) : value = (4+8) * (8+1) = 108 (5, 6, 1) : value = (5+6) * (6+1) = 77 (4, 6, 1) : value = (4+6) * (6+1) = 70 Sum of special triplets = 747
इस समस्या का एक सरल समाधान सरणी से सभी ट्रिपल उत्पन्न कर रहा है। सभी विशेष त्रिगुणों के लिए, उपरोक्त सूत्र का उपयोग करके इसके मान की गणना करना। और फिर उन्हें एक योग चर में जोड़ें और अंतिम योग लौटाएं।
उदाहरण
समाधान का वर्णन करने के लिए कार्यक्रम,
#include <iostream>
using namespace std;
int findSpecialTripletSum(int X[], int Y[], int Z[], int sizeX, int sizeY, int sizeZ) {
int sum = 0;
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
for (int k = 0; k < sizeZ; k++) {
if (X[i] <= Y[j] && Z[k] <= Y[j])
sum = sum + (X[i] + Y[j]) * (Y[j] + Z[k]);
}
}
}
return sum;
}
int main() {
int X[] = {5, 9, 4};
int Y[] = {8, 6};
int Z[] = {7, 1};
int sizeX = sizeof(X) / sizeof(X[0]);
int sizeY = sizeof(Y) / sizeof(Y[0]);
int sizeZ = sizeof(Z) / sizeof(Z[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(X, Y, Z,
sizeX, sizeY, sizeZ);
} आउटपुट
Sum of special triplets = 747
सरणी X और Z को क्रमबद्ध करके एक और अधिक कुशल समाधान हो सकता है। फिर उन तत्वों की जांच करें जो सरणी Y के प्रत्येक तत्व के लिए विशेष ट्रिपल आवश्यकता को पूरा करते हैं।
तो, सरणी Y यानी Y [i] के सूचकांक i पर किसी भी तत्व के लिए। सरणी X {x1, x2} और Z {z1, z2} के तत्व, Y[i] से कम हैं, फिर
मानों का योग,
S = (x1+Y[i])(Y[i]+z1) + (x1+Y[i])(Y[i]+z2) + (x2+Y[i])(Y[i]+z1) + (x2+Y[i])(Y[i]+z2) S = (x1+Y[i])(Y[i]+z1+Y[i]+z2) + (x2+Y[i])(Y[i]+z1+Y[i]+z2) S = (2Y[i] + x1 + x2)(2y[i] + z1 + z2)
N =X में Y[i] से अधिक तत्वों की संख्या
M =Z में Y[i] से अधिक तत्वों की संख्या
Sx =X में Y[i] से अधिक तत्वों का योग
Sz =Z में Y[i] से अधिक तत्वों का योग
S = (N*Y[i] + Sx) * (M*Y[i] + Sz)
उदाहरण
उपरोक्त समाधान को स्पष्ट करने के लिए कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
int tripletSumCalc(int X[], int Y[], int Z[], int prefixSumA[], int prefixSumC[], int sizeA, int sizeB, int sizeC){
int totalSum = 0;
for (int i = 0; i < sizeB; i++) {
int currentElement = Y[i];
int n = upper_bound(X, X + sizeA, currentElement) - X;
int m = upper_bound(Z, Z + sizeC, currentElement) - Z;
if (n == 0 || m == 0)
continue;
totalSum += ((prefixSumA[n - 1] + (n * currentElement)) * (prefixSumC[m - 1] + (m * currentElement)));
}
return totalSum;
}
int* findPrefixSum(int* arr, int n) {
int* prefixSumArr = new int[n];
prefixSumArr[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
return prefixSumArr;
}
int findSpecialTripletSum(int A[], int B[], int C[], int sizeA, int sizeB, int
sizeC){
int specialTripletSum = 0;
sort(A, A + sizeA);
sort(C, C + sizeC);
int* prefixSumA = findPrefixSum(A, sizeA);
int* prefixSumC = findPrefixSum(C, sizeC);
return tripletSumCalc(A, B, C, prefixSumA, prefixSumC, sizeA, sizeB, sizeC);
}
int main() {
int A[] = {5, 9, 4};
int B[] = {8, 6};
int C[] = {7, 1};
int sizeA = sizeof(A) / sizeof(A[0]);
int sizeB = sizeof(B) / sizeof(B[0]);
int sizeC = sizeof(C) / sizeof(C[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(A, B, C, sizeA, sizeB, sizeC);
} आउटपुट
Sum of special triplets = 747