Table of Contents

## Problem Statement

In the “Minimum number of Merge Operations to make an Array Palindrome” problem we have given an array “a[]”. Find the minimum number of merge_operations are required to make an array palindrome. Note, A palindrome is a word, phrase, or sequence that reads the same backward as forwards.

## Input Format

The first line containing an integer n.

Second-line containing n integer separated by space(” “).

## Output Format

The first and only one line containing an integer value which denotes the minimum number of merge_operations to make an array palindrome.

## Constraints

- 1<=n<=10^5
- 1<=a[i]<=10^6

## Example

5 23 45 65 45 23

0

**Explanation: **Given array is already a palindrome, So the number of operations took is 0.

4 1 7 9 1

1

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

5 1 3 8 6 1

2

Here the minimum number of merge operations took is 2 to make it a palindrome.

## Algorithm

**1.** Create two variables i,j. i will point to the start of the array and j to the end.

Till iĀ less then 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.

## Implementation

### C++ Program for Minimum number of Merge Operations to make an Array Palindrome

#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; } int ans = 0; for (int i=0,j=n-1; i<=j;) { if(a[i]==a[j]) { i++; j--; } else if(a[i]>a[j]) { j--; a[j]+=a[j+1] ; ans++; } else { i++; a[i]+=a[i-1]; ans++; } } cout<<ans<<endl; return 0; }

### Java Program for Minimum number of Merge Operations to make an Array Palindrome

import java.util.Scanner; class sum { public static void main(String[] args) { Scanner sr = new Scanner(System.in); int n=sr.nextInt(); int a[]= new int[n]; for(int i=0;i<n;i++) { a[i]=sr.nextInt(); } int ans = 0; for (int i=0,j=n-1; i<=j;) { if(a[i]==a[j]) { i++; j--; } else if(a[i]>a[j]) { j--; a[j]+=a[j+1] ; ans++; } else { i++; a[i]+. =a[i-1]; ans++; } } System.out.println(ans); } }

7 1 2 3 5 3 2 4

4

## Complexity Analysis

### Time Complexity

**O(n)** where **n** is the size of the given array. Here we visit the array once and find the desired answer.

### Space Complexity

**O(1)** because we don’t declare any auxiliary space here.