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’. The only allowed operation is”merging” (of two adjacent elements). Merging two adjacent elements means replacing them with their sum. The task is to find the minimum number of merge operations required to make the given array a ‘Palindrome’.

To make any array a palindrome, we can simply apply merge operation n-1 times where n is the size of the array (because a single-element array is always palindromic, similar to single-character string). In that case, the size of array will be reduced to 1. But in this problem, we are asked to do it in the minimum number of operations.

Example : 

Input : arr[] = {15, 4, 15}
Output : 0
Array is already a palindrome. So we
do not need any merge operation.

Input : arr[] = {1, 4, 5, 1}
Output : 1
We can make given array palindrome with
minimum one merging (merging 4 and 5 to
make 9)

Input : arr[] = {11, 14, 15, 99}
Output : 3
We need to merge all elements to make
a palindrome.

The expected time complexity is O(n).

Let f(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 at index i or index j. Our answer in this case will be f(i+1, j-1).
2. Else, we need to do merging operations. Following cases arise.
   • 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).
   • 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 the size of array arr[].

Therefore this problem can be solved iteratively using two pointers (first pointer pointing to start of the array and second pointer pointing to the last element of the array) method and keeping count of total merging operations done till now.

Below is an implementation of the above idea.

Count of minimum operations is 1

Time Complexity: O(n)
Auxiliary Space: O(1)

This article is contributed by Ashish Jain. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Approach#2: Using dynamic programming

Create a 2D array dp of size n x n where n is the length of the input array arr. Initialize all elements of dp to 0. For each gap value from 1 to n – 1, loop over all i values from 0 to n – gap – 1. Compute the corresponding j value as i + gap. If arr[i] is equal to arr[j], then set dp[i][j] to dp[i + 1][j – 1].Otherwise, set dp[i][j] to min(dp[i][j – 1], dp[i + 1][j]) + 1. The minimum number of merge operations required to make arr a palindrome is dp[0][n – 1].

Algorithm

1. Initialize count variable to 0.
2. Initialize two pointers i and j to the start and end of the array respectively.
3. While i is less than j,
a. If arr[i] is equal to arr[j], increment i and decrement j.
b. Else, if arr[i] is less than arr[j], increment i by 1 and add arr[i-1] to arr[i]. Increment count by 1.
c. Else, decrement j by 1 and add arr[j+1] to arr[j]. Increment count by 1.
4. Return count.

3

Time Complexity: O(n), where n is length of array
Auxiliary Space: O(1)