একটি পূর্ণসংখ্যা Number দেওয়া থাকলে, ১ থেকে Number পর্যন্ত মান ধারণকারী অ্যারেটি Number-1 বার নিচের অপারেশন দিয়ে রিডিউস করতে হবে:
অ্যারে থেকে দুটি এলিমেন্ট
AওBবেছে নিন।উনাদের অ্যারে থেকে সরিয়ে
A² + B²যোগ করুন।
শেষে একটি মাত্র পূর্ণসংখ্যা থাকবে; লক্ষ্য হলো সেই মান সর্বাধিক করা।
প্রায়োরিটি কিউ ব্যবহার
সর্বোচ্চ ফলাফলের জন্য সর্বোচ্চ
AওBবেছে নেওয়া উচিত।প্রায়োরিটি কিউ (max-heap) দিয়ে সর্বোচ্চ দুটি এলিমেন্ট বের করা হয়।
দুটি এলিমেন্ট পপ করিয়ে তাদের বর্গের যোগফল আবার পুশ করুন।
এটি
Number-1বার চলবে।
উদাহরণ
ইনপুট − Number = 2
আউটপুট − অ্যারে রিডাকশনের পর একক এলিমেন্ট: 5
ব্যাখ্যা − অ্যারে [1,2], PQ: 2,1। A=2,B=1 → 4+1=5।
ইনপুট − Number = 5
আউটপুট − অ্যারে রিডাকশনের পর একক এলিমেন্ট: 1187163713
ব্যাখ্যা − ধাপে ধাপে বর্গের যোগফল বেড়ে যাওয়া দেখানো হয়েছে।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
প্রায়োরিটি কিউতে ১ থেকে N পর্যন্ত মান পুশ করুন। প্রতিবার শীর্ষ দুটি মান পপ করিয়ে বর্গের যোগফল পুশ করুন। শেষে শীর্ষ মান ফেরত দিন।
ইনপুট
Numberনিন।lliটাইপডেফ ব্যবহার করুন।reduceArray(int Num)ফাংশন ফলাফল ফেরত দেয়।priority_queueঘোষণা করুন।pQueue while(i<=Num) pQueue.push(i++)দিয়ে পূরণ করুন।while(pQueue.size() > 1)লুপে শীর্ষ দুটি পপ করিয়ে বর্গের যোগফল পুশ করুন।শেষে
pQueue.top()ফেরত দিন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
priority_queue 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
