Minimum number of Merge Operations to make an Array Palindrome

January 29, 2021

A minimum number of Merge Operations to make an Array Palindrome in Java.

Problem Statement:

Given an array of positive integers, write a program to find the 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 backward as forwards.

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

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

Algorithm:

Create two variables i,j. i will point to the start of the array and j to the end.
Till i less than or equal to j
If arr[i] = arr[j], then there is no need to merge the elements. Increment i and decrement j
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
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

Java code :

class prepinsta
{
    public static int minoperation(int[] arr, int n)
    {
        int output = 0;
        for (int i=0,j=n-1; i<=j;)
        {
            if (arr[i] == arr[j])
            {
                i++;
                j–;
            }
            else if (arr[i] > arr[j])
            {
                j–;
                arr[j] += arr[j+1] ;
                output++;
            }
            else
            {
                i++;
                arr[i] += arr[i-1];
                output++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 7, 9, 1} ;
        System.out.println(“Minimum operations to be done : “+ minoperation(arr, arr.length));
    }
}

Output :

Minimum operations to be done : 1