Minimum number of Merge Operations to make an Array Palindrome

June 23, 2019

Given an array of positive integers, write a program to find minimum number of merge operations required to make the array palindrome

 

If it is not a palindrome it will make merge operations and prints the number of merge operations. In each merge operation it will merge two adjacent elements. Here, merging two elements means replacing them with their sum.

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards.

Example

Input :
arr[] = {23, 45, 65, 45, 23}

Output :
Array is already a palindrome, So the number of operations took is 0

Input :
arr[] = {1, 7, 9, 1}

Output :
Number of merge operations are 1. mereging 7, 9 makes the array palindrome

Input :
arr[] = {1,3,8,6,1}

Output :
Minimum no of merge operations took is 2 to make it a palindrome.

Time Complexity : O(n)

Algorithm

Create two variables i,j. i will point to the start of the array and j to the end.
Till i  less then or equal to j

a. If arr[i] = arr[j], then there is no need to merge the elements. Increment i and decrement j

b. If arr[i] > arr[j], then do merge operation at index j ie, arr[j-1] = arr[j-1] + arr[j], decrement j and increment the no of merge operations count by 1

c.  If arr[i] < arr[j], then do merge operation at index i ie, arr[i+1] = arr[i+1] + arr[i], increment i and increment the no of merge operations count by 1

Readers are requested to submit their codes in different languages in comment section below. .Best codes will be selected and published on website.

Code

[code language=”cpp”]

#include <iostream>
using namespace std;

int minOperatins(int arr[], int n) //This function takes the array and size of the array and returns the min no of operations
{
int ops = 0, i=0, j= n-1; //Starting from left end and right end
while(i<=j)
{
if(arr[i]==arr[j])// If the left element is equal to right element no need to merge
{
i++;
j–;
}
else if(arr[i]>arr[j]) //if the left element is greater than right element then merge right two elements
{
arr[j-1]=arr[j-1]+arr[j];
j–;
ops++;
}
else //if the right element is greater than left element then merge left two elements
{
arr[i+1]=arr[i+1]+arr[i];
i++;
ops++;
}
}
return ops;
}

int main()
{
int arr[]= {1,3,8,6,1};
int n = sizeof(arr)/sizeof(arr[0]);
int ans = minOperatins(arr, n);

if(ans == 0)
{
cout<<"array is already a palindrome"<<endl<<"Minimum no of merge operations took is "<< ans;
}
else if(ans==n-1)
{
cout<<"merging all elements to get a palindrome"<<endl<<"Minimum no of merge operations took is "<< ans;
}
else
{
cout<<"Minimum no of merge operations took is "<< ans;
}
return 0;
}

[/code]