এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে n সংখ্যক ধনাত্মক সংখ্যা থাকে। আমাদের কাজ হলো অ্যারেটিকে প্যালিনড্রোম बनाने জন্য ন্যূনতম মার্জ অপারেশন খুঁজে বের করা।
প্যালিনড্রোম অ্যারে
প্যালিনড্রোম অ্যারে প্যালিনড্রোম স্ট্রিং-এর মতো, যেখানে 인ডেক্স i এবং n-i-এ উপস্থিত উপাদানগুলো একই থাকে।
উদাহরণ
{5, 1, 7, 2, 7, 1, 5}
সমস্যা বিবরণ
আমাদের অ্যারেটিকে প্যালিনড্রোম করতে হবে এবং একমাত্র বৈধ অপারেশন হলো মার্জ অপারেশন যেখানে আমরা i এবং i+1 ইনডেক্সের উপাদানগুলো যোগ করব।
আমাদের প্রদত্ত অ্যারেটিকে প্যালিনড্রোম করার জন্য ন্যূনতম ilyen অপারেশন খুঁজে বের করতে হবে।
উদাহরণ
ইনপুট
arr[] = {4, 1, 7, 6, 1, 5}
আউটপুট
2
ব্যাখ্যা
আমাদের দুটি মার্জ অপারেশন দরকার:
- ইনডেক্স ০ এবং ১-এ মার্জ করলে অ্যারে হয় {5, 7, 6, 1, 5}
- তারপর ইনডেক্স ২ এবং ৩-এ মার্জ করলে অ্যারে হয় {5, 7, 7, 5}
সমাধানের পদ্ধতি
সমস্যাটি সমাধানের একটি সহজ পদ্ধতি হলো টু পয়েন্টার ব্যবহার করে স্ট্রিং প্যালিনড্রোম করার মতো। আমরা start এবং end পয়েন্টার ব্যবহার করব। যদি দুটি পয়েন্টার মিলে যায় (start == end), তবে অ্যারেটি প্যালিনড্রোম। আমরা start এবং end পয়েন্টার দিয়ে লুপ চালাব এবং নিম্নলিখিত শর্তগুলো অনুযায়ী অপারেশন করব:
- যদি arr[start] == arr[end], তবে বর্তমান ইনডেক্সের জন্য প্যালিনড্রোম শর্ত পূরণ হয়। আমরা তাদের পরবর্তী ইনডেক্সে নেব। অর্থাৎ start++ এবং end--।
- যদি arr[start] > arr[end], তবে end ইনডেক্সের জন্য মার্জ অপারেশন করতে হবে এবং mergeCount ১ বাড়াব।
- যদি arr[start] < arr[end], তবে start ইনডেক্সের জন্য মার্জ অপারেশন করতে হবে এবং mergeCount ১ বাড়াব।
start == end হলে merge count ফেরত দিব।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
int findMergeCount(int arr[], int n){
int mergeCount = 0;
int start = 0;
int end = n-1;
while(start <= end){
if (arr[start] == arr[end]){
start++;
end--;
}
else if (arr[start] > arr[end]){
end--;
arr[end] += arr[end+1];
mergeCount++;
}
else {
start++;
arr[start] += arr[start-1];
mergeCount++;
}
}
return mergeCount;
}
int main(){
int arr[] = {4, 1, 7, 6, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The minimum number of merge operations required to make the array palindrome is " << findMergeCount(arr, n);
return 0;
}
আউটপুট
The minimum number of merge operations required to make the array palindrome is 2
