Find minimum number of merge operations to make an array palindrome

By | May 29, 2016

Find minimum number of merge operations to make an array palindrome

In this post we try to convert a given array into a palindrome by using minimum number of merge operations.

Find minimum number of merge operations to make an array palindrome

Given an array of positive integers. We need to make the given array a ‘Palindrome’.

A Palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.Only allowed operation on array is merge. Here, Merging two adjacent elements means replacing them with their sum.

The task is to find minimum number of merge operations required to make given array a ‘Palindrome’.To make an array a palindromic we can simply apply merging operations n-1 times where n is the size of array (Note a single element array is always palindrome similar to single character string). In that case, size of array will be reduced to 1. But in this problem we are asked to do it in minimum number of operations.

Find minimum number of merge operations to make an array palindrome example

Input Array: { 5, 3, 4, 5 }
Output: 1
The given array can be merged and made into palindrome by adding 3 and 4.
Input Array: { 7, 8, 1, 3 }
Output: 3
The given array can be made a palindrome only by adding all the elements one by one.

 

Find minimum number of merge operations to make an array palindrome solution

We solve this problem iteratively using two pointers one pointing to the start and other pointing to the last element of the array.We keep a track of the merging operations done till now.

Let m(i, j) be minimum merging operations to make subarray arr[i..j] a palindrome.
If i == j answer is 0. We start i from 0 and j from n-1.

  1. If arr[i] == arr[j], then there is no need to do any merging operations . Answer in this case will be f(i+1, j-1).
  2. Else, we need to do merging operations. Following cases arise.
    1. If arr[i] > arr[j], then we should do merging operation at index j. We merge index j-1 and j, and update arr[j-1] = arr[j-1] + arr[j]. Our answer in this case will be 1 + f(i, j-1).
    2. For the case when arr[i] < arr[j], update arr[i+1] = arr[i+1] + arr[i]. Our answer in this case will be 1 + f(i+1, j).
  3. Our answer will be f(0, n-1), where n is size of array arr[].

Find minimum number of merge operations to make an array palindrome solution code in c++:

#include <bits/stdc++.h>
using namespace std;

// required to make arr[] palindrome
int FindMinOps(int arr[], int n)
{
    int ans = 0; // Initialize result
 
    // Start from two corners
    for (int i=0,j=n-1; i<=j;)
    {
        // If corner elements are same,
        // problem reduces arr[i+1..j-1]
        if (arr[i] == arr[j])
        {
            i++;
            j--;
        }
 
        // If left element is greater, then
        // we merge right two elements
        else if (arr[i] > arr[j])
        {
            // need to merge from tail.
            j--;
            arr[j] += arr[j+1] ;
            ans++;
        }
 
        // Else we merge left two elements
        else
        {
            i++;
            arr[i] += arr[i-1];
            ans++;
        }
    }
 
    return ans;
}
 
// Driver program to test above
int main()
{
    int arr[] = {1, 3, 5, 8, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of minimum operations is "
         <<  FindMinOps(arr, n) << endl;
    return 0;
}

 Output:

Count of minimum operations is 1

Time Complexity: O(N)
Space Complexity:O(1)