Find minimum number of merge operation to make an array palindrome

Given an array of integers, the task is to make the array a palindrome in minimum number of operations possible.The only operation allowed to do so is merging of two elements. Merging operation symbolizes replacing the two elements with the sum of those two elements.

A palindrome array is an array that reads the same backward and forward.

Example

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)

Approach

The given problem can be solved using a two pointer approach.

Step 1 : Initialize two pointers i and j at the start and end of the array respectively.

Hence, i = 0 and j= n-1; where, n = size of the given array.

Step 2 : Initialize an answer counter to keep track of the number of merge operations performed.

Step 3 : While i <= j :

1. If array[i] == array[j], there is no need for any merging operations. Increase i and decrease j by one.
2. Else if array[i] < array[j], merge array[i] and array[i+1]. Update array[i+1] = array[i] + array[i+1] and move i to the left by one place ( i = i+1 ). Increment the answer counter.
3. Else if array[j] < array[i], merge array[j] and array[j-1]. Update array[j-1] = array[j] + array[j-1] and move j to the right by one place ( j = j-1 ). Increment the answer counter.

Step 4 : Return the answer.

Complexity

• Time Complexity: O(N), where N = the size of the given array.
• Space Complexity:  O(1)

Java Code

import java.util.Arrays;

class MergeArrayForPalindrome {

    // Returns minimum number of count operations
    // required to make arr[] palindrome

    static 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 method to test the above function
    public static void main(String[] args){

        int arr[] = new int[]{1, 4, 5, 9, 1} ;

        System.out.println("Input array: " + Arrays.toString(arr));

        System.out.println("Count of minimum operations is "+

            findMinOps(arr, arr.length));

    }

}

Output

Input array: [1, 4, 5, 9, 1]
Count of minimum operations is 1