ধরি target নামক একটি ইন্টিজার অ্যারে দেওয়া আছে। একটি শুরুতেই সব 1-বিশিষ্ট অ্যারে A থেকে নিচের প্রসেস অনুসরণ করে target অ্যারে তৈরি করা সম্ভব কিনা তা যাচাই করতে হবে –
x := বর্তমানে অ্যারেতে থাকা সব উপাদানের যোগফল
0 থেকে n-1 পরিসরের একটি ইন্ডেক্স i বেছে নিন এবং A[i] = x সেট করুন
এই প্রসেস যেকোনো সংখ্যক বার दुহরা सकते हैं
target অ্যারে A-থেকে তৈরি করা সম্ভব কিনা তা চেক করুন, না হলে False ফেরত দিন।
ইনপুট যদি [3,9,5] হয়, তবে আউটপুট True, কারণ [1,1,1] থেকে শুরু করে ইন্ডেক্স 0-এ যোগফল 3 সেট করলে [3,1,1], তারপর যোগফল 5 ইন্ডেক্স 2-এ সেট করলে [3,1,5], তারপর যোগফল 9 ইন্ডেক্স 1-এ সেট করলে [3,9,5] পাওয়া যায়।
সমাধানের ধাপসমূহ
sum := 0
n := target এর আকার
i := 0 থেকে n-1 পর্যন্ত লুপ চালিয়ে sum += target[i] করুন
target অ্যারে দিয়ে একটি প্রায়োরিটি কিউ (pq) ইনিশিয়ালাইজ করুন
যখন pq-এর উপরের উপাদান > sum, লুপ চালান –
x := pq-এর উপরের উপাদান
pq থেকে উপাদান মুছুন
pq-তে (2 * x - sum) যোগ করুন
sum := x
যদি sum == target এর আকার হয় তবে true, অন্যথায় false ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#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
