- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In this problem, we are given an array arr[] consisting of n positive numbers. Our task is to Find minimum number of merge operations to make an array palindrome.

**Palindrome array** are similar to palindrome strings, the elements at index i and n-i should be the same.

{5, 1, 7, 2, 7, 1, 5}

**Problem Description** − We need to make the array palindrome by performing operations on it. And the only operation which is valid on the array is the merge operation in which we will add elements at index i and i+1.

We need to return the minimum number of such operations required to make the given array palindrome.

**Let’s take an example to understand the problem,**

arr[] = {4, 1, 7, 6, 1, 5}

2

We need two merge operations,

Merging elements at index 0 and 1, makes the array {5, 7, 6, 1, 5}.

After this merging elements at index 2 and 3, makes the array {5, 7, 7, 5}.

A simple solution to the problem is by finding the number of operations to make the string palindrome. This is done by using two pointers start and end. If both the points meet i.e. start == end the array is a palindrome. So, we will loop for start and end pointer and perform the operation based on these conditions −

If arr[start] == arr[end], this means for the current index, the array satisfies palindrome condition. For will move them to the next index. I.e. start++ and end--.

If arr[start] > arr[end], in this case we need to perform the merge operation for the end index and increment the mergeCount by 1.

If arr[start] < arr[end], in this case we need to perform the merge operation for the start index and increment the mergeCount by 1.

We will return the merge count when the start == end.

**Program to illustrate the working of our solution,**

#include <iostream> using namespace std; int findMergeCount(int arr[], int n){ int mergeCount = 0; int start = 0; int end = n-1; while(start <= end){ if (arr[start] == arr[end]){ start++; end--; } else if (arr[start] > arr[end]){ end--; arr[end] += arr[end+1] ; mergeCount++; } else { start++; arr[start] += arr[start-1]; mergeCount++; } } return mergeCount; } int main(){ int arr[] = {4, 1, 7, 6, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"The minimum number of merge operations required to make the array palindrome is "<<findMergeCount(arr, n); return 0; }

The minimum number of merge operations required to make the array palindrome is 2

- Related Questions & Answers
- Find minimum operations needed to make an Array beautiful in C++
- Minimum number of operations on an array to make all elements 0 using C++.
- Minimum operations to make XOR of array zero in C++
- Minimum number of deletions to make a string palindrome in C++.
- Program to find minimum operations to make array equal using Python
- Minimum number of Appends needed to make a string palindrome in C++
- Minimum delete operations to make all elements of array same in C++.
- Program to find minimum number of operations required to make one number to another in Python
- Minimum operations to make GCD of array a multiple of k in C++
- Program to find minimum operations to make the array increasing using Python
- Minimum removal to make palindrome permutation in C++
- Minimum operations required to remove an array in C++
- Program to find minimum number of operations required to make lists strictly Increasing in python
- Minimum number of given operations required to make two strings equal using C++.
- Program to find minimum number of characters to be added to make it palindrome in Python

Advertisements