সমস্যা বিবরণ
একটি অ্যারে এবং ইন্টিজার k দেওয়া থাকলে, অ্যারে থেকে কিছু এলিমেন্ট বেছে নিতে হবে যাতে তাদের গুণফল সর্বোচ্চ হয়। শর্ত: প্রোডাক্টে যেসব এলিমেন্ট একাধিকবার আছে, তাদের ফ্রিকোয়েন্সি সম্মিলিত (frequency sum) 2×k-এর চেয়ে বেশি হবে না।
সমাধানের পদ্ধতি
- অ্যারে সর্ট করুন।
- প্রতিটি ইউনিক এলিমেন্ট একবার করে গুণ করুন (প্রোডাক্টে যোগ করুন)।
- ফ্রিকোয়েন্সি ম্যাপ বানান।
- সর্বোচ্চ মান থেকে শুরু করে পিছিয়ে আসুন:
- যদি k >= (freq-1) হয়, তবে সেই এলিমেন্ট (freq-1) বার যোগ করুন, k কমান।
- যদি k < (freq-1) হয়, তবে k বার যোগ করুন এবং ব্রেক।
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 = product * arr[i];
}
s[arr[i]] = s[arr[i]] + 1;
}
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 = k - s[arr[j]] + 1;
s[arr[j]] = 0;
}
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
ব্যাখ্যা
সর্টেড: [2,5,5,6,6,7,8,8]
ইউনিক গুণফল: 2×5×6×7×8 = 3360
k=2, ফ্রিকোয়েন্সি: 5(2),6(2),8(2)
এক্সট্রা: 8^(2-1)=8, 6^(2-1)=6 → k=0
মোট = 3360 × 8 × 6 = 161280
জটিলতা
- সময়: O(n log n)
- স্থান: O(n)
