এই সমস্যায়, আমাদেরকে 3টি অ্যারে X, Y, Z দেওয়া হয়েছে৷ আমাদের কাজ হল 3টি অ্যারে থেকে উপাদান সম্বলিত বিশেষ ট্রিপলেটগুলির সমষ্টি খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা৷
বিশেষ ট্রিপলেট একটি বিশেষ ধরনের ট্রিপলেট যা নিম্নলিখিত সম্পত্তি −
ধারণ করেএর জন্য (a, b, c):a ≤ b এবং b ≥ c, অর্থাৎ ট্রিপলেটের মাঝের উপাদানটি অন্য দুটির থেকে অভিবাদন করা উচিত।
এবং, ট্রিপলেটের মান −
সূত্র দ্বারা দেওয়া হয়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
