सी ++ में एकाधिक रकम के साथ लक्ष्य सरणी का निर्माण करें

मान लीजिए कि हमारे पास पूर्णांक लक्ष्य की एक सरणी है। सभी 1 से मिलकर एक प्रारंभिक सरणी A से, हम निम्नलिखित प्रक्रिया कर सकते हैं -

• विचार करें कि x वर्तमान में हमारे सरणी में सभी तत्वों का योग है।

• इंडेक्स i चुनें, 0 से n तक, जहां n सरणी का आकार है और इंडेक्स i से x पर A का मान सेट करें।

• हम इस प्रक्रिया को जितनी बार चाहें उतनी बार दोहरा सकते हैं।

हमें यह जांचना होगा कि क्या ए से लक्ष्य सरणी बनाना संभव है अन्यथा झूठी वापसी करें।

इसलिए, यदि इनपुट [3,9,5] जैसा है, तो आउटपुट ट्रू होगा, जैसा कि हम इंडेक्स [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

• जब योग लक्ष्य के आकार के समान हो, अन्यथा असत्य हो, तो सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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