Arrays: Get minimum number of merge operations to make an array palindrome

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