C++ में आवृत्ति प्रतिबंध के साथ सरणी से अधिकतम गुणनफल

सरणी और पूर्णांक k दिया गया है। सरणी से तत्व चुनकर अधिकतम गुणनफल प्राप्त करें ताकि दोहराए जाने वाले तत्वों की आवृत्ति का योग 2*k से अधिक न हो।

रणनीति: सरणी को सॉर्ट करें। पहले प्रत्येक अद्वितीय तत्व को एक बार लें। फिर शेष k का उपयोग करके सबसे बड़े तत्वों की अतिरिक्त प्रतियां गुणा करें।

उदाहरण: {5, 6, 7, 8, 2, 5, 6, 8}, k=2 → अधिकतम गुणनफल 161280।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

#define ll long long int

ll maxProd(int arr[], int n, int k) {
    ll product = 1;
    unordered_map s;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        if (s[arr[i]] == 0) product *= arr[i];
        s[arr[i]]++;
    }
    for (int j = n - 1; j >= 0 && k > 0; j--) {
        if (k > (s[arr[j]] - 1) && (s[arr[j]] - 1) > 0) {
            product *= pow(arr[j], s[arr[j]] - 1);
            k -= s[arr[j]] - 1;
            s[arr[j]] = 0;
        } else if (k <= (s[arr[j]] - 1) && (s[arr[j]] - 1) > 0) {
            product *= pow(arr[j], k);
            break;
        }
    }
    return product;
}

int main() {
    int arr[] = {5, 6, 7, 8, 2, 5, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxProd(arr, n, k);
    return 0;
}

आउटपुट

161280