इस समस्या में, हमें 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} बनती है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान सरणी को पैलिंड्रोम बनाने के लिए आवश्यक संचालनों की संख्या खोजना है। यह दो पॉइंटर्स start और end का उपयोग करके किया जाता है। यदि दोनों पॉइंटर्स मिलते हैं (start == end), तो सरणी पैलिंड्रोम है। इसलिए, हम start और end पॉइंटर के लिए लूप चलाएंगे और निम्न शर्तों के आधार पर संचालन करेंगे:
- यदि arr[start] == arr[end], तो वर्तमान इंडेक्स के लिए सरणी पैलिंड्रोम शर्त को पूरा करती है। हम उन्हें अगले इंडेक्स पर ले जाएँगे: start++ और end--।
- यदि arr[start] > arr[end], तो हमें end इंडेक्स के लिए मर्ज संचालन करना होगा और mergeCount को 1 से बढ़ाना होगा।
- यदि arr[start] < arr[end], तो हमें start इंडेक्स के लिए मर्ज संचालन करना होगा और mergeCount को 1 से बढ़ाना होगा।
हम start == end होने पर merge count लौटाएँगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
उदाहरण
#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
