C++ এ একই গড় দিয়ে বিভক্ত অ্যারে

ধরুন আমাদের একটি অ্যারে A আছে, আমাদের অবশ্যই A-এর প্রতিটি উপাদানকে তালিকা B বা তালিকা C-তে স্থানান্তর করতে হবে। (এই তালিকা B এবং C প্রাথমিকভাবে খালি।) আমাদের পরীক্ষা করতে হবে যে এই ধরনের সরানোর পরে, এটা সম্ভব যে গড় মান B এর গড় C এর গড় মানের সমান, এবং B এবং C উভয়ই খালি নয়।

তাই যদি ইনপুট − [1,2,3,4,5,6,7,8,9,10] এর মত হয়, তাহলে ফলাফল সত্য হবে,

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=A এর আকার, মোট :=0
• আরম্ভ করার জন্য i :=0, যখন i করুন
• মোট :=মোট + A[i]

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool splitArraySameAverage(vector<int>& A) {
      int n = A.size();
      int total = 0 ;
      for(int i = 0; i < n; i++) total += A[i];
      bool isPossible = false;
      int m = n / 2;
      for (int i = 1; i <= m && !isPossible; ++i)
      if (total*i%n == 0) isPossible = true;
      if (!isPossible) return false;
      vector < vector <bool> > dp(total + 1, vector <bool>((n / 2) + 1));
      dp[0][0] = true;
      for(int i = 0; i < n; i++){
         int x = A[i];
         for(int j = total; j >= x; j--){
            for(int l = 1; l <= (n / 2); l++){
               dp[j][l] = dp[j][l] || dp[j - x][l - 1];
            }
         }
      }
      for(int i = 1 ; i <= (n / 2); i++){
         if((total * i) % n == 0 && dp[total * i / n][i]) return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10};
   cout << (ob.splitArraySameAverage(v));
}

ইনপুট

{1,2,3,4,5,6,7,8,9,10}

আউটপুট

1