Find Minimum Operations to Make an Array Palindrome

Understanding the Problem

The goal is to determine the minimum number of merge operations required to make an array a palindrome.

Method 1: Two-Pointer Approach

This method uses a two-pointer technique to check and merge elements as needed.

#include <iostream>
using namespace std;

int minOperations(int arr[], int n) {
    int i = 0, j = n - 1, operations = 0;
    while (i < j) {
        if (arr[i] == arr[j]) {
            i++; j--;
        } else if (arr[i] < arr[j]) {
            arr[i + 1] += arr[i];
            i++;
            operations++;
        } else {
            arr[j - 1] += arr[j];
            j--;
            operations++;
        }
    }
    return operations;
}

int main() {
    int arr[] = {1, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum operations: " << minOperations(arr, n) << endl;
    return 0;
}
            

Output:

Minimum operations: 1

Method 2: Recursion

This method uses a recursive approach to count the operations.

#include <iostream>
using namespace std;

int minOpsRecursive(int arr[], int i, int j) {
    if (i >= j) return 0;
    if (arr[i] == arr[j]) return minOpsRecursive(arr, i + 1, j - 1);
    if (arr[i] < arr[j]) {
        arr[i + 1] += arr[i];
        return 1 + minOpsRecursive(arr, i + 1, j);
    } else {
        arr[j - 1] += arr[j];
        return 1 + minOpsRecursive(arr, i, j - 1);
    }
}

int main() {
    int arr[] = {1, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum operations: " << minOpsRecursive(arr, 0, n - 1) << endl;
    return 0;
}
            

Output:

Minimum operations: 1

Method 3: Dynamic Programming

This method utilizes a DP table to compute the minimum operations.

#include <iostream>
#include <cstring>
using namespace std;

int minOpsDP(int arr[], int n) {
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    for (int gap = 1; gap < n; ++gap) {
        for (int i = 0, j = gap; j < n; ++i, ++j) {
            dp[i][j] = (arr[i] == arr[j]) ? dp[i + 1][j - 1] :
                        (1 + ((arr[i] < arr[j]) ? dp[i + 1][j] : dp[i][j - 1]));
        }
    }
    return dp[0][n - 1];
}

int main() {
    int arr[] = {1, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum operations: " << minOpsDP(arr, n) << endl;
    return 0;
}
            

Output:

Minimum operations: 1