এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে যা এন ধনাত্মক সংখ্যার সমন্বয়ে গঠিত। আমাদের কাজ হল একটি অ্যারে প্যালিনড্রোম তৈরি করতে ন্যূনতম সংখ্যক মার্জ অপারেশন খুঁজে বের করা।
প্যালিনড্রোম অ্যারে প্যালিনড্রোম স্ট্রিংগুলির মতো, সূচক i এবং n-i-এর উপাদানগুলি একই হওয়া উচিত৷
উদাহরণ
{5, 1, 7, 2, 7, 1, 5} সমস্যা বর্ণনা − আমাদের এটিতে অপারেশন করে অ্যারে প্যালিনড্রোম তৈরি করতে হবে। এবং একমাত্র অপারেশন যা অ্যারেতে বৈধ তা হল মার্জ অপারেশন যেখানে আমরা সূচী i এবং i+1 এ উপাদান যোগ করব।
প্রদত্ত অ্যারে প্যালিনড্রোম তৈরি করার জন্য আমাদের এই ধরনের ন্যূনতম সংখ্যক ক্রিয়াকলাপ ফেরত দিতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 1, 7, 6, 1, 5} আউটপুট
2
ব্যাখ্যা
আমাদের দুটি মার্জ অপারেশন দরকার,
সূচক 0 এবং 1 এ উপাদানগুলিকে একত্রিত করা, অ্যারে তৈরি করে {5, 7, 6, 1, 5}৷
সূচক 2 এবং 3-এ এই উপাদানগুলিকে একত্রিত করার পরে, অ্যারে তৈরি করে {5, 7, 7, 5}৷
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল স্ট্রিং প্যালিনড্রোম তৈরির জন্য অপারেশনের সংখ্যা খুঁজে বের করা। এটি শুরু এবং শেষ দুটি পয়েন্টার ব্যবহার করে করা হয়। যদি উভয় বিন্দু মিলিত হয় অর্থাৎ শুরু ==শেষ হয় অ্যারেটি একটি প্যালিনড্রোম। সুতরাং, আমরা স্টার্ট এবং এন্ড পয়েন্টার লুপ করব এবং এই শর্তগুলির উপর ভিত্তি করে অপারেশন করব -
-
যদি arr[start] ==arr[end] হয়, তাহলে বর্তমান সূচকের জন্য এর অর্থ হল, প্যালিনড্রোম অবস্থাকে সন্তুষ্ট করে। জন্য পরবর্তী সূচক তাদের সরানো হবে. অর্থাৎ শুরু++ এবং শেষ--।
-
যদি arr[start]> arr[end] হয়, এই ক্ষেত্রে আমাদের শেষ সূচকের জন্য মার্জ অপারেশন করতে হবে এবং মার্জকাউন্ট 1 দ্বারা বৃদ্ধি করতে হবে।
-
যদি arr[start]
শুরু ==শেষ হলে আমরা মার্জ গণনা ফেরত দেব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
