# Minimum number of Merge Operations to make an Array Palindrome  Difficulty Level Easy
Array Math

## 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```

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.
Ugly Number Leetcode Solution

## 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.