Minimum number of Merge Operations to make an Array Palindrome

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

1. 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

C++ Program

#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;
}
Try It


Next > < Prev
Scroll to Top