Tích tối đa từ mảng sao cho tổng tần số của tất cả các phần tử lặp lại trong tích nhỏ hơn hoặc bằng 2 * k trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tích tối đa từ mảng sao cho tổng tần suất của tất cả các phần tử lặp lại trong tích nhỏ hơn hoặc bằng 2 * k.

Đối với điều này, chúng ta sẽ được cung cấp một mảng và một số nguyên k. Nhiệm vụ của chúng ta là tìm tích lớn nhất từ ​​mảng cho trước mà tổng tần suất của tất cả các chữ số phải nhỏ hơn hoặc bằng 2 * k.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
//returning maximum product value
ll maxProd(int arr[], int n, int k) {
   ll product = 1;
   unordered_map<int, int> s;
   sort(arr, arr + n);
   for (int i = 0; i < n; i++) {
      if (s[arr[i]] == 0) {
         product = product * arr[i];
      }
      //storing values in hash map
      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;
}

Đầu ra

161280