Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में अपडेट के साथ रेंज में अधिकतम गुणनफल जोड़ी ढूंढने की क्वेरी

इस समस्या में, हमें एक ऐरे arr[] और Q क्वेरी दी गई हैं। प्रत्येक क्वेरी 2 प्रकार की हो सकती है, 1. दी गई रेंज [Start - End] में अधिकतम जोड़ी गुणनफल ढूंढना। 2. i-वें इंडेक्स तत्व को मान से अपडेट करना। हमारा कार्य C++ में अपडेट के साथ रेंज में अधिकतम गुणनफल जोड़ी ढूंढने की क्वेरी को हल करने के लिए एक प्रोग्राम बनाना है।

उदाहरण से समझते हैं

इनपुट: arr = {4, 2, 6, 9, 1}

Q = 3

Q1 = [1, 1, 4]

Q2 = [2, 2, 3]

Q3 = [1, 0, 2]

आउटपुट: 54, 12

व्याख्या

क्वेरी 1, टाइप 1 के लिए: रेंज = {2, 6, 9, 1}। अधिकतम गुणनफल 6*9 = 54

क्वेरी 2, टाइप 2 के लिए: i = 2, अपडेटेड ऐरे arr[] = {4, 2, 3, 9, 1}

क्वेरी 3, टाइप 1 के लिए: रेंज = {4, 2, 3}। अधिकतम गुणनफल 4*3 = 12

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हमारे पास एक सरल दृष्टिकोण है। जो टाइप 1 की हर क्वेरी के लिए पूरे ऐरे को ट्रैवर्स करना और हर जोड़ी के गुणनफल की जांच करना और फिर उनमें से अधिकतम गुणनफल जोड़ी ढूंढना है।

C++ प्रोग्राम उदाहरण (सरल दृष्टिकोण)

#include <iostream>
using namespace std;

int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}

int findMaxProductPair(int arr[], int n, int start, int end) {
    int maxProd = 0;
    for (int i = start; i <= end; i++) {
        for (int j = i + 1; j <= end; j++) {
            maxProd = max(maxProd, (arr[i] * arr[j]));
        }
    }
    return maxProd;
}

int main() {
    int arr[] = {4, 2, 6, 9, 1, 5};
    int n = 6;
    int Q = 3;
    int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
    for (int i = 0; i < Q; i++) {
        if (query[i][0] == 1) {
            cout << "The maximum product pair in the range is " << findMaxProductPair(arr, n, query[i][1], query[i][2]) << "\n";
        } else if (query[i][0] == 2) {
            cout << "Updating values...\n";
            arr[query[i][1]] = query[i][2];
        }
    }
    return 0;
}

आउटपुट

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12

यह दृष्टिकोण अच्छा है लेकिन अधिकतम गुणनफल ढूंढने के लिए, हमें पूरे ऐरे को ट्रैवर्स करना होगा जो समय जटिलता को बढ़ाता है।

कुशल समाधान: सेगमेंट ट्री डेटा संरचना

एक कुशल समाधान सेगमेंट ट्री डेटा संरचना का उपयोग करके सब-ऐरे के दो सबसे बड़े तत्वों को स्टोर करना हो सकता है। और फिर उनका गुणनफल वापस करना।

C++ प्रोग्राम उदाहरण (कुशल दृष्टिकोण: सेगमेंट ट्री)

#include <iostream>
using namespace std;

struct segment {
    int maxEle;
    int secMax;
};

segment findMaxProductPair(segment* prodTree, int index, int start, int end, int L, int R) {
    segment result;
    result.maxEle = -1;
    result.secMax = -1;
    if (L > end || R < start || start > end)
        return result;
    if (start >= L && end <= R)
        return prodTree[index];
    int middleIndex = (start + end) / 2;
    segment left = findMaxProductPair(prodTree, 2 * index, start, middleIndex, L, R);
    segment right = findMaxProductPair(prodTree, 2 * index + 1, middleIndex + 1, end, L, R);
    result.maxEle = max(left.maxEle, right.maxEle);
    result.secMax = min(max(left.maxEle, right.secMax), max(right.maxEle, left.secMax));
    return result;
}

void update(segment* prodTree, int index, int start, int end, int i, int updateVal) {
    if (i < start || i > end)
        return;
    if (start == end) {
        prodTree[index].maxEle = updateVal;
        prodTree[index].secMax = -1;
        return;
    }
    int middleIndex = (start + end) / 2;
    update(prodTree, 2 * index, start, middleIndex, i, updateVal);
    update(prodTree, 2 * index + 1, middleIndex + 1, end, i, updateVal);
    prodTree[index].maxEle = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
    prodTree[index].secMax = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
}

void buildtree(segment* prodTree, int* arr, int index, int start, int end) {
    if (start > end) {
        return;
    }
    if (start == end) {
        prodTree[index].maxEle = arr[start];
        prodTree[index].secMax = -1;
        return;
    }
    int middleIndex = (start + end) / 2;
    buildtree(prodTree, arr, 2 * index, start, middleIndex);
    buildtree(prodTree, arr, 2 * index + 1, middleIndex + 1, end);
    int maximum = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
    int secMaximum = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
    prodTree[index].maxEle = maximum;
    prodTree[index].secMax = secMaximum;
}

int main() {
    int arr[] = {4, 2, 6, 9, 1, 5};
    int n = 6;
    int Q = 3;
    segment* prodTree = new segment[4 * n + 1];
    buildtree(prodTree, arr, 1, 0, n - 1);
    int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
    for (int i = 0; i < Q; i++) {
        if (query[i][0] == 1) {
            segment result = findMaxProductPair(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
            cout << "The maximum product pair in the range is " << (result.maxEle * result.secMax) << "\n";
        } else if (query[i][0] == 2) {
            cout << "Updating values...\n";
            update(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
        }
    }
    return 0;
}

आउटपुट

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12
  1. - C++ में सरणी में अधिकतम GCD वाली जोड़ी ढूंढना

    मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी है। हमारा कार्य सरणी से पूर्णांकों की जोड़ी ढूंढना है, जहां GCD मान अधिकतम है। मान लीजिए A = {1, 2, 3, 4, 5}, तो आउटपुट 2 है। जोड़ी (2, 4) का GCD 2 है, अन्य GCD मान 2 से कम हैं।इस समस्या को हल करने के लिए, हम एक काउंट सरणी बनाए रखेंगे जो प्रत्येक तत्

  1. - C++ में LCM उत्पाद के बराबर होने वाले अधिकतम लंबाई के सबएरे

    मान लीजिए हमारे पास एक सरणी A है। हमें सबएरे की अधिकतम लंबाई ढूंढनी है, जिसका LCM उस सबएरे के एलिमेंट्स के उत्पाद के समान है। यदि ऐसा सबएरे नहीं मिलता, तो -1 वापस करें। मान लीजिए सरणी {6, 10, 21} है, तो लंबाई 2 है, क्योंकि सबएरे {10, 21} है, जिसका LCM 210 है, और उत्पाद भी 210 है। दृष्टिकोण सीधा है।

  1. - C++ में रेंज सम क्वेरीज विदाउट अपडेट्स

    समस्या विवरण यहां हम देखेंगे कि सरणी में इंडेक्स i से इंडेक्स j तक के तत्वों का योग कैसे प्राप्त करें। यह मूल रूप से रेंज क्वेरी है। कार्य केवल इंडेक्स i से j तक एक लूप चलाकर और योग की गणना करके आसान है। लेकिन हमें इस बात का ध्यान रखना होगा कि इस तरह की रेंज क्वेरी कई बार निष्पादित की जाएगी। इसलिए