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

Introduction

Given an array of positive integers. We need to make the given collection a ‘Palindrome.’ The only allowed operation is” merging” (of two adjacent elements). Joining two neighboring parts implies supplanting them with their aggregate. The undertaking is to find the base number of consolidation tasks expected to make the given cluster a 'Palindrome.'

To make any cluster a palindrome, we can just apply to combine activity n-multiple times where n is the size of the assortment (on the grounds that a solitary component exhibit is dependably palindromic, like a solitary person string). All things considered, the size of the display will be decreased to 1. However, in this issue, we are requested to do it in the base number of activities.

Also Read About, Array Implementation of Queue and  Rabin Karp Algorithm

Minimum number of merge operations to make an array palindrome

We can easily tackle the issue by keeping two pointers, I and j, that at first focus on the two endpoints of array arr, i.e., the principal pointer I focus on the index of the primary array element, and the second pointer j focuses to the index of the last array element. Then circle till the inquiry space is depleted and diminish search space arr[i, j] at every circle cycle.

In every cycle of the circle, we look at the elements present at index I and j and play out the merge procedure on the lesser weight side, i.e., merge element arr[i] with element arr[i+1] if arr[i] < arr[j] and increase I, merge element arr[j] with element arr[j-1] when arr[i] > arr[j] and decrement j; in any case, overlook both the elements when arr[i] == arr[j].

Example

Input : arr[] = {15, 4, 15}

Output : 0

Array is already a palindrome.No merge required

Input : arr[] = {1, 4, 5, 1}

Output : 1

We can make given array palindrome with one merge 

Input : arr[] = {11, 14, 15, 99}

Output : 3

We need to merge all elements to make a palindrome.

The time complexity of the above arrangement is O(n) and requires no additional room, where n is the size of the info.

Problem-solving implementation

Let f(i, j) be the least consolidating task to make subarray arr[i..j] a palindrome. If I == j answer is 0. We start I from 0 and j from n-1.

On the off chance that arr[i] == arr[j], there is a compelling reason to do any blending tasks at index I or index j. Our response for this situation will be f(i+1, j-1).

Else, we want to do blending tasks. Following cases emerge.

In the event that arr[i] > arr[j], we ought to do blending activity at index j. We merge index j-1 and j, and update arr[j-1] = arr[j-1] + arr[j]. Our response for this situation will be 1 + f(i, j-1).

For the situation when arr[i] < arr[j], update arr[i+1] = arr[i+1] + arr[i]. Our response for this situation will be 1 + f(i+1, j).

Our response will be f(0, n-1), where n is the size of array arr[].

Consequently, this issue can be addressed iteratively by utilizing the two-pointers technique and keeping count of absolute consolidating activities done work now.

C++ Code

// C++ program to find number of operations
// to make an array palindrome
#include <bits/stdc++.h>
using namespace std;

// Returns minimum number of count operations
// 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, 4, 5, 9, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of minimum operations is "
        << findMinOps(arr, n) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:  

The count of minimum operations is 1

Algorithm:

Array [26, 5, 7, 25]

while (i <=j)
{
   If ( arr[i] > arr[j]
      j- - ;
      arr[j] = arr[j] + avr[j+1];
   }
   else if ( arr[i] < avr[j]) 
   {
      i++
      arr[i] = arr[i]+arr[i-1] ;
   }
  else { i++ j--;}
}

Check out this problem - Check If A String Is Palindrome

You can also read about Palindrome Number in Python here.

Read also - Strong number in c