ধরুন আমাদের লক্ষ্য পূর্ণসংখ্যার একটি অ্যারে আছে। সমস্ত 1 এর সমন্বয়ে গঠিত একটি প্রারম্ভিক অ্যারে A থেকে, আমরা নিম্নলিখিত পদ্ধতিটি সম্পাদন করতে পারি -
-
এখন আমাদের অ্যারেতে থাকা সমস্ত উপাদানের যোগফল x কে বিবেচনা করুন।
-
সূচক i বেছে নিন, 0 থেকে n পরিসরে, যেখানে n হল অ্যারের আকার এবং সূচী i থেকে x এ A-এর মান সেট করুন।
-
আমরা যতবার প্রয়োজন ততবার এই পদ্ধতিটি পুনরাবৃত্তি করতে পারি।
A থেকে টার্গেট অ্যারে তৈরি করা সম্ভব কিনা তা আমাদের পরীক্ষা করতে হবে অন্যথায় False রিটার্ন করুন।
সুতরাং, যদি ইনপুটটি [3,9,5] এর মত হয়, তাহলে আউটপুটটি True হবে, যেমন আমরা ইনডেক্স [1,1,1] দিয়ে শুরু করতে পারি, তারপর সূচক 0 এ যোগফল 3 হয়, তারপর অ্যারেটি [3] ,1,1], তারপর যোগফল হল 5, সূচক 2 এ, তারপর অ্যারে হল [3,1,5], তারপর যোগফল হল 9, সূচক 1 এ, সুতরাং অ্যারে হল [3,9,5]৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
যোগফল :=0
-
n :=লক্ষ্যের আকার
-
আরম্ভ করার জন্য i :=0, যখন i
-
যোগফল :=যোগফল + লক্ষ্য[i]
-
-
অগ্রাধিকার সারি pq সংজ্ঞায়িত করুন, এবং লক্ষ্য অ্যারে দিয়ে এটি শুরু করুন
-
pq> যোগফলের শীর্ষ উপাদান, −
করুন-
x :=pq
এর শীর্ষ উপাদান -
pq
থেকে উপাদান মুছুন -
2 * x - pq এ যোগ করুন
-
যোগফল :=x
-
-
যোগফল টার্গেটের আকারের সমান হলে true ফেরত দিন, অন্যথায় মিথ্যা
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool isPossible(vector<int>& target) {
lli sum = 0;
int n = target.size();
for (int i = 0; i < n; i++) {
sum += target[i];
}
priority_queue<int> pq(target.begin(), target.end());
while (pq.top() * 2 > sum) {
int x = pq.top();
pq.pop();
pq.push(2 * x - sum);
sum = x;
}
return sum == (int)target.size();
}
};
main(){
Solution ob;
vector<int> v = {3,9,5};
cout << (ob.isPossible(v));
} ইনপুট
{3,9,5} আউটপুট
1
