C++-এ তিনটি অ্যারে থেকে স্পেশাল ট্রিপলেটের যোগফল

এই সমস্যাতে, আমাদের ৩টি অ্যারে X, Y, Z দেওয়া আছে। আমাদের কাজ হলো তিনটি অ্যারে থেকে এলিমেন্ট নিয়ে স্পেশাল ট্রিপলেটের যোগফল বের করার প্রোগ্রাম লিখা।

স্পেশাল ট্রিপলেট হলো একটি বিশেষ ধরনের ট্রিপলেট যেটি নিচের প্রোপার্টি ধারণ করে −

(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[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