एक पूर्णांक चर Number इनपुट के रूप में दिया गया है। आइए 1 से Number तक की सीमा में किसी भी क्रम में तत्वों वाली एक सरणी पर विचार करें। यदि हम एक सरणी पर Number-1 बार एक संक्रिया करते हैं जैसे कि
हम सरणी से दो तत्व A और B चुनते हैं
A और B को सरणी से हटाते हैं
A और B के वर्गों का योग सरणी में जोड़ते हैं
अंत में हमें एकल पूर्णांक मान मिलेगा; लक्ष्य है उस तत्व के लिए अधिकतम संभव मान ढूंढना।
प्राथमिकता कतार का उपयोग
अंतिम परिणाम को अधिकतम करने के लिए, हमें A और B को इस तरह चुनना होगा कि वे अधिकतम हों।
अधिकतम A और B ढूंढने के लिए, हम मानों को संग्रहीत करने के लिए एक प्राथमिकता कतार का उपयोग करेंगे।
एक प्राथमिकता कतार तत्वों को घटते क्रम में संग्रहीत करती है।
सबसे ऊपर का तत्व मूल्य में सबसे बड़ा होता है और इसी तरह। इसलिए दो तत्वों को पॉप करने के बाद हम उनके वर्गों को फिर से कतार में पुश करेंगे।
वांछित परिणाम प्राप्त करने के लिए Number - 1 बार पॉप और पुश करेंगे।
उदाहरण
इनपुट - Number=2
आउटपुट - सरणी कमी के बाद एकल तत्व: 5
व्याख्या - मान लें सरणी में तत्व [ 1 2 ] हैं
प्राथमिकता कतार में डालने के बाद: 2 1
A=5, B=4: A2+B2=1+4=5
अंतिम तत्व: 5
इनपुट - Number=5
आउटपुट - सरणी कमी के बाद एकल तत्व: 1187163713
व्याख्या - मान लें सरणी में तत्व [ 5 1 2 4 3 ] हैं
प्राथमिकता कतार में डालने के बाद: 5 4 3 2 1
A=5, B=4: A2+B2=25+16=41: 41 3 2 1
A=41, B=3: A2+B2=1681+9=1690: 1690 2 1
A=1690, B=2: A2+B2=1681+4=2856104: 2856104 1
A=2856104, B=1: A2+B2=1187163712+1=1187163713: 1187163713
अंतिम तत्व: 1187163713
उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम तत्वों को घटते क्रम में संग्रहीत करने के लिए प्राथमिकता कतार का उपयोग करेंगे। शीर्ष दो सबसे बड़े तत्वों को पॉप करें और दोनों के वर्गों का योग फिर से उस कतार में पुश करें। इसे तब तक करें जब तक केवल एक मान शेष न रह जाए।
इनपुट वेरिएबल Number लें।
परिणामों के लिए डेटा प्रकार long long int - lli लें
फ़ंक्शन reduceArray(int Num) इनपुट नंबर लेता है और उपरोक्त संक्रियाओं का उपयोग करके गणना किया गया अधिकतम एकल पूर्णांक लौटाता है।
priority_queue के रूप में pQueue लें।
while लूप का उपयोग करके 1 से N तक की संख्याओं से pQueue भरें।
जब i<=Num, pQueue में i पुश करें
अब pQueue में पूर्णांक 1 से N घटते क्रम में हैं और आकार N है।
अब while लूप का उपयोग करके pQueue को तब तक ट्रैवर्स करें जब तक इसका आकार >=1 न हो।
var1 = pQueue.top() के रूप में अधिकतम लें और इसे पॉप करें।
var2 = pQueue.top() के रूप में अगला अधिकतम लें और इसे पॉप करें।
var1 को इसका वर्ग और var2 को इसका वर्ग सेट करें।
var1+var2 को pQueue में फिर से पुश करें।
while लूप के अंत में, शीर्ष तत्व लौटाएं।
main के अंदर परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h> using namespace std; #define lli long long int int reduceArray(int Num){ priority_queue<lli> pQueue; int i=1; while(i<=Num){ pQueue.push(i); i=i+1; } while (pQueue.size() > 1) { lli var1 = pQueue.top(); pQueue.pop(); lli var2 = pQueue.top(); pQueue.pop(); var1=var1*var1; var2=var2*var2; pQueue.push(var1+var2); } return pQueue.top(); } int main(){ int Number = 5; cout<<"Single element after array reduction: "<<reduceArray(Number); return 0; } आउटपुट
उपरोक्त कोड चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:
Single element after array reduction: 1187163713