সি++-এ একই গড় বিশিষ্ট অ্যারে ভাগ করা (Split Array With Same Average)

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

যেমন, ইনপুট [1,2,3,4,5,6,7,8,9,10] হলে, ফলাফল হবে true।

সমাধানের ধাপসমূহ

• n := A.size(), total := 0
• i := 0 থেকে n-1 পর্যন্ত total += A[i]
• isPossible := false, m := n / 2
• i := 1 থেকে m পর্যন্ত এবং !isPossible পর্যন্ত লুপ চালান
  • যদি (total * i) % n == 0 হয়, তবে isPossible := true
• যদি !isPossible হয়, তবে false রিটার্ন করুন
• (total + 1) x (n/2 + 1) আকারের একটি ২D dp অ্যারে সংজ্ঞায়িত করুন
• dp[0][0] := true
• প্রতিটি উপাদান x := A[i] এর জন্য
  • j := total থেকে x পর্যন্ত কমাতে হয়
    • l := 1 থেকে n/2 পর্যন্ত
      • dp[j][l] := dp[j][l] OR dp[j-x][l-1]
• i := 1 থেকে n/2 পর্যন্ত
  • যদি (total * i) % n == 0 এবং dp[total * i / n][i] সত্য হয়, তবে true রিটার্ন করুন
• false রিটার্ন করুন

উদাহরণ

#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