Minimum number of Merge Operations to make an Array Palindrome

Difficulty Level Easy
Frequently asked in Amazon
Array MathViews 4036

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.

Translate »