Find the minimum number of merge operations to make an array palindrome
Given a list of non-negative integers, find the minimum number of merge operations to make it a palindrome. A merge operation can only be performed on two adjacent elements. The result of a merge operation is that the two adjacent elements are replaced with their sum.
For example,
Output: 1
Explanation: [6, 1, 3, 7] —> Merge 6 and 1 —> [7, 3, 7]
Input: [6, 1, 4, 3, 1, 7]
Output: 2
Explanation: [6, 1, 4, 3, 1, 7] —> Merge 6 and 1 —> [7, 4, 3, 1, 7] —> Merge 3 and 1 —> [7, 4, 4, 7]
Input: [1, 3, 3, 1]
Output: 0
Explanation: The list is already a palindrome
We can easily solve the problem by maintaining two pointers, i and j, that initially points to both endpoints of array arr, i.e., the first pointer i points to the index of the first array element and the second pointer j points to the index of the last array element. Then loop till the search space is exhausted and reduce search space arr[i, j] at each iteration of the loop.
In each iteration of the loop, we compare the elements present at index i and j and perform the merge operation on the lesser weight side, i.e., merge element arr[i] with element arr[i+1] if arr[i] < arr[j] and increment i, merge element arr[j] with element arr[j-1] when arr[i] > arr[j] and decrement j; otherwise, ignore both the elements when arr[i] == arr[j].
Following is the C, Java, and Python implementation based on the idea:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <stdio.h> // Function to find the minimum number of merge operations to make a // given array palindrome int findMin(int arr[], int n) { // stores the minimum number of merge operations needed int count = 0; // `i` and `j` initially points to endpoints of the array int i = 0, j = n - 1; // loop till the search space is exhausted while (i < j) { if (arr[i] < arr[j]) { // merge item at i'th index with the item at (i+1)'th index arr[i + 1] += arr[i]; i++, count++; } else if (arr[i] > arr[j]) { // merge item at (j-1)'th index with the item at j'th index arr[j - 1] += arr[j]; j--, count++; } // otherwise, ignore both the elements else { i++, j--; } } return count; } int main(void) { int arr[] = { 6, 1, 4, 3, 1, 7 }; int n = sizeof(arr) / sizeof(arr[0]); int min = findMin(arr, n); printf("The minimum number of operations required is %d", min); return 0; } |
Output:
The minimum number of operations required is 2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Main { // Function to find the minimum number of merge operations to make a // given array palindrome private static int findMin(int[] arr) { // stores the minimum number of merge operations needed int count = 0; // `i` and `j` initially points to endpoints of the array int i = 0, j = arr.length - 1; // loop till the search space is exhausted while (i < j) { if (arr[i] < arr[j]) { // merge item at i'th index with the item at (i+1)'th index arr[i + 1] += arr[i]; i++; count++; } else if (arr[i] > arr[j]) { // merge item at (j-1)'th index with the item at j'th index arr[j - 1] += arr[j]; j--; count++; } // otherwise, ignore both the elements else { i++; j--; } } return count; } public static void main(String[] args) { int[] arr = { 6, 1, 4, 3, 1, 7 }; int min = findMin(arr); System.out.println("The minimum number of operations required is " + min); } } |
Output:
The minimum number of operations required is 2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# Function to find the minimum number of merge operations to make a # given array palindrome def findMin(arr): # stores the minimum number of merge operations needed count = 0 # `i` and `j` initially points to endpoints of the array i = 0 j = len(arr) - 1 # loop till the search space is exhausted while i < j: if arr[i] < arr[j]: # merge item at i'th index with the item at (i+1)'th index arr[i + 1] += arr[i] i = i + 1 count = count + 1 elif arr[i] > arr[j]: # merge item at (j-1)'th index with the item at j'th index arr[j - 1] += arr[j] j = j - 1 count = count + 1 # otherwise, ignore both the elements else: i = i + 1 j = j - 1 return count if __name__ == '__main__': arr = [6, 1, 4, 3, 1, 7] min = findMin(arr) print("The minimum number of operations required:", min) |
Output:
The minimum number of operations required is 2
The time complexity of the above solution is O(n) and doesn't require any extra space, where n is the size of the input.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)