C++ में 3 सरणियों के तत्वों वाले विशेष त्रिकों का योग

समस्या विवरण

इस समस्या में, हमें 3 सरणी X, Y, Z दी गई हैं। हमारा कार्य 3 सरणियों के तत्वों वाले विशेष त्रिकों (special triplets) का योग ज्ञात करने के लिए एक प्रोग्राम बनाना है।

विशेष त्रिक एक विशेष प्रकार का त्रिक है जो निम्नलिखित गुण रखता है -

(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) : मान = (5+8) * (8+7) = 195
(5, 8, 1) : मान = (5+8) * (8+1) = 117
(4, 8, 7) : मान = (4+8) * (8+7) = 180
(4, 8, 1) : मान = (4+8) * (8+1) = 108
(5, 6, 1) : मान = (5+6) * (6+1) = 77
(4, 6, 1) : मान = (4+6) * (6+1) = 70
विशेष त्रिकों का योग = 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 << "विशेष त्रिकों का योग = " << findSpecialTripletSum(X, Y, Z, sizeX, sizeY, sizeZ);
}

आउटपुट

विशेष त्रिकों का योग = 747

एक और अधिक कुशल समाधान सरणी X और Z को क्रमबद्ध (sort) करके हो सकता है। फिर सरणी Y के प्रत्येक तत्व के लिए उन तत्वों की जांच करें जो विशेष त्रिक की आवश्यकता को पूरा करते हैं।

तो, सरणी Y के इंडेक्स i पर किसी भी तत्व यानी 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 << "विशेष त्रिकों का योग = " << findSpecialTripletSum(A, B, C, sizeA, sizeB, sizeC);
}

आउटपुट

विशेष त्रिकों का योग = 747