इस समस्या में, हमें n धनात्मक संख्याओं से युक्त एक सरणी arr[] दिया जाता है। हमारा कार्य सरणी पैलिंड्रोम बनाने के लिए न्यूनतम संख्या में मर्ज संचालन का पता लगाना है।
पैलिंड्रोम सरणी पैलिंड्रोम स्ट्रिंग्स के समान हैं, इंडेक्स 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], इस मामले में हमें अंतिम इंडेक्स के लिए मर्ज ऑपरेशन करने और मर्जकाउंट को 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