Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Minimum number of merge operations to make an array palindrome
2.1.
Example
2.2.
Problem-solving implementation
2.3.
C++ Code
2.4.
Algorithm:
3.
Frequently Asked Questions
3.1.
How would you make an array palindrome?
3.2.
Is the base number of tasks' expectation to make the capacity worth of all arrays rise?
3.3.
What number of most minor activities could you have to perform to make every one of the elements of equivalent?
3.4.
How would you make a palindrome?
3.5.
How would you make a palindrome from a string?
4.
Conclusion
Last Updated: Mar 27, 2024

Find the minimum number of merge operations to make an array palindrome

Author Adya Tiwari
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Given an array of positive integers. We need to make the given collection a ‘Palindrome.’ The only allowed operation is” merging” (of two adjacent elements). Joining two neighboring parts implies supplanting them with their aggregate. The undertaking is to find the base number of consolidation tasks expected to make the given cluster a 'Palindrome.'

To make any cluster a palindrome, we can just apply to combine activity n-multiple times where n is the size of the assortment (on the grounds that a solitary component exhibit is dependably palindromic, like a solitary person string). All things considered, the size of the display will be decreased to 1. However, in this issue, we are requested to do it in the base number of activities.

Also Read About, Array Implementation of Queue and  Rabin Karp Algorithm

Minimum number of merge operations to make an array palindrome

We can easily tackle the issue by keeping two pointers, I and j, that at first focus on the two endpoints of array arr, i.e., the principal pointer I focus on the index of the primary array element, and the second pointer j focuses to the index of the last array element. Then circle till the inquiry space is depleted and diminish search space arr[i, j] at every circle cycle.

In every cycle of the circle, we look at the elements present at index I and j and play out the merge procedure on the lesser weight side, i.e., merge element arr[i] with element arr[i+1] if arr[i] < arr[j] and increase I, merge element arr[j] with element arr[j-1] when arr[i] > arr[j] and decrement j; in any case, overlook both the elements when arr[i] == arr[j].

Example

Input : arr[] = {15, 4, 15}

Output : 0

Array is already a palindrome.No merge required

Input : arr[] = {1, 4, 5, 1}

Output : 1

We can make given array palindrome with one merge 

Input : arr[] = {11, 14, 15, 99}

Output : 3

We need to merge all elements to make a palindrome.

The time complexity of the above arrangement is O(n) and requires no additional room, where n is the size of the info.

Problem-solving implementation

Let f(i, j) be the least consolidating task to make subarray arr[i..j] a palindrome. If I == j answer is 0. We start I from 0 and j from n-1.

On the off chance that arr[i] == arr[j], there is a compelling reason to do any blending tasks at index I or index j. Our response for this situation will be f(i+1, j-1).

Else, we want to do blending tasks. Following cases emerge.

In the event that arr[i] > arr[j], we ought to do blending activity at index j. We merge index j-1 and j, and update arr[j-1] = arr[j-1] + arr[j]. Our response for this situation will be 1 + f(i, j-1).

For the situation when arr[i] < arr[j], update arr[i+1] = arr[i+1] + arr[i]. Our response for this situation will be 1 + f(i+1, j).

Our response will be f(0, n-1), where n is the size of array arr[].

Consequently, this issue can be addressed iteratively by utilizing the two-pointers technique and keeping count of absolute consolidating activities done work now.

C++ Code

// C++ program to find number of operations
// to make an array palindrome
#include <bits/stdc++.h>
using namespace std;

// Returns minimum number of count operations
// required to make arr[] palindrome
int findMinOps(int arr[], int n)
{
    int ans = 0; // Initialize result

    // Start from two corners
    for (int i=0,j=n-1; i<=j;)
    {
        // If corner elements are same,
        // problem reduces arr[i+1..j-1]
        if (arr[i] == arr[j])
        {
            i++;
            j--;
        }

        // If left element is greater, then
        // we merge right two elements
        else if (arr[i] > arr[j])
        {
            // need to merge from tail.
            j--;
            arr[j] += arr[j+1] ;
            ans++;
        }

        // Else we merge left two elements
        else
        {
            i++;
            arr[i] += arr[i-1];
            ans++;
        }
    }

    return ans;
}

// Driver program to test above
int main()
{
    int arr[] = {1, 4, 5, 9, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of minimum operations is "
        << findMinOps(arr, n) << endl;
    return 0;
}

Output:  

The count of minimum operations is 1

Algorithm:

Array [26, 5, 7, 25]

while (i <=j)
{
   If ( arr[i] > arr[j]
      j- - ;
      arr[j] = arr[j] + avr[j+1];
   }
   else if ( arr[i] < avr[j]) 
   {
      i++
      arr[i] = arr[i]+arr[i-1] ;
   }
  else { i++ j--;}
}

Check out this problem - Check If A String Is Palindrome

You can also read about Palindrome Number in Python here.

Read also - Strong number in c

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How would you make an array palindrome?

To make any array a palindrome, we can essentially apply merge activity n-multiple times where n is the size of the collection (because a solitary element array is consistently palindromic, like a single-character string).

Is the base number of tasks' expectation to make the capacity worth of all arrays rise?

If the information array is = {1, 2, 3, 4} we require at least three activities to make all elements equivalent. For instance, we can create element 4 by completing 3 increments.

What number of most minor activities could you have to perform to make every one of the elements of equivalent?

On the off chance that the information array is = {1, 2, 3, 4} we require at least three tasks to make all elements equivalent. For instance, we can create element 4 by completing 3 increases.

How would you make a palindrome?

You should simply work out the word, expression, or sentence, follow it with "sides turned around is," and afterward rehash the word, phrase, and sentence backward request.

How would you make a palindrome from a string?

Given a string s, we want to advise most minor characters to be affixed (inclusion toward the finish) to make a string palindrome.

Conclusion

We have recollected that when we want to make the given array a 'Palindrome.' The main permitted activity is"merging" (of two nearby elements). Combining two contiguous elements implies supplanting them with their total. The undertaking is to find the base number of merge tasks expected to make the given array a 'Palindrome.'

To make any array a palindrome, we can just apply merge activity n-multiple times where n is the size of the collection (because a solitary element array is dependably palindromic, like a single-character string).

Recommended Readings:

Recommended problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in PygameCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass