Minimum number of Merge Operations to make an Array Palindrome  

Difficulty Level Easy
Frequently asked in Amazon
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.

Please click Like if you loved this article?

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.
See also
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.

Please click Like if you loved this article?