Problem Statement:
You are given an array, you need to find the minimum number of merge operations to be performed to make the array as a palindrome.
You can only merge 2 adjacent elements.
Example:
arr[] = {1, 4, 5, 1} Output: 1 Here if you merge [4,5], the resultant array will be [1, 9, 1] which is a palindrome array. Hence the minimum number of merge operations is 1.
Solution:
Here we take 2 pointers, first pointer pointing to the beginning of the array. Second pointer pointing to the end of the array.
Then when we compare any 2 elements, we get following 3 cases:
1. arr[i] = arr[j]
2. arr[i] < arr[j]
3. arr[i] > arr[j]
Now we need to define the steps that needs to be done at each case:
If arr[i] = arr[j], then increment i and decrement j by 1.
If arr[i] < arr[j], then update arr[i+1] = arr[i+1] + arr[i]. Then increment i.
If arr[i] > arr[j], then update arr[j-1] = arr[j-1] + arr[j]. Then decrement j.
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <queue> using namespace std; int find_min_operations(int arr[], int n) { int result = 0; for (int i=0,j=n-1; i<=j;) { //case 1 if (arr[i] == arr[j]) { i++; j--; } //case 2 else if (arr[i] > arr[j]) { j--; arr[j] += arr[j+1] ; result++; } // case 3 else { i++; arr[i] += arr[i-1]; result++; } } return result; } int main() { int arr[] = {1, 4, 5, 1}; int n = sizeof(arr)/sizeof(arr[0]); cout << "The minimum number of merge operations are " << find_min_operations(arr, n) << endl; return 0; }
Output:
The minimum number of merge operations are 1