Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and help us grow. Happy coding 🙂
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,
Input: [6, 1, 3, 7]
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] 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
// 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.