Minimum Number of Moves to Make Palindrome
Minimum Number of Moves to Make Palindrome
Minimum Number of Moves to Make Palindrome – A palindrome is a sequence that reads the same from both ends. For example, [1, 2, 3, 2, 1] is a palindrome because it is the same when read from left to right and from right to left.
In this blog, we’ll explore how to make an array a palindrome using the minimum number of merge operations. A merge operation in this context means adding two adjacent elements and replacing them with their sum.
Problem Statement: Minimum Number of Moves to Make Palindrome
You are given an array consisting of positive integers. Your task is to convert this array into a palindrome by performing the minimum number of merge operations.
- A merge operation means selecting two adjacent elements, adding them together, and replacing those two elements with their sum.
- This operation reduces the size of the array by 1. The new number formed by the merge replaces the two numbers at their positions.
- The goal is to perform such operations as few times as possible so that the final array becomes a palindrome.
What is a Palindrome?
A palindrome is a sequence that reads the same forwards and backwards.
For example:
- [1, 2, 3, 2, 1] is a palindrome.
- [7, 3, 3, 7] is also a palindrome.
- But [1, 2, 3] is not a palindrome.
Merge Operation Rule:
- You can only merge adjacent elements.
- The operation must be done in-place—modifying the original array.
- Each merge counts as 1 operation.
- You are allowed to perform merges on either side (left or right).
Your Task: Write an efficient program that calculates the minimum number of merge operations needed to make the given array a palindrome.
Input Format:
A single array arr[] of n positive integers
- 1 ≤ arr[i] ≤ 10^4
- 1 ≤ n ≤ 10^5
Output Format:
- A single integer denoting the minimum number of merge operations required to make the array a palindrome.
Example
Let’s take an example to understand the problem:
Input:
arr[] = {1, 4, 5, 9, 1}
Output:
1
Explanation:
We merge 4 + 5 = 9 to get {1, 9, 9, 1} → which becomes a palindrome.
Hence, only 1 merge operation is required.
C++ Code: Minimum Number of Moves to Make Palindrome
C++ Code
#include <iostream>
using namespace std;
int minMergeOperations(int arr[], int n) {
int ans = 0;
int left = 0, right = n - 1;
while (left < right) {
if (arr[left] == arr[right]) {
left++;
right--;
}
else if (arr[left] < arr[right]) {
arr[left + 1] += arr[left];
left++;
ans++;
}
else {
arr[right - 1] += arr[right];
right--;
ans++;
}
}
return ans;
}
int main() {
int arr[] = {1, 4, 5, 9, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum merge operations = " << minMergeOperations(arr, n);
return 0;
}Output:
Minimum merge operations = 1
Algorithm for Minimum Number of Moves to Make Palindrome
- Initialize two pointers left = 0 and right = n – 1.
- If arr[left] == arr[right], move both pointers inward.
- If arr[left] < arr[right], merge arr[left] with arr[left + 1], increment left, and count the merge.
- If arr[left] > arr[right], merge arr[right] with arr[right – 1], decrement right, and count the merge.
- Continue this process until left >= right.
- Return the total number of merge operations.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Example with Step-by-Step Algorithm
Example 1:
Input:
arr[] = {11, 14, 15, 99}
Steps:
- left = 0, right = 3 → 11 != 99
- Since 11 < 99, merge 11 + 14 = 25, new array: {25, 15, 99}
- left = 1, right = 2 → 25 != 99
- Since 25 < 99, merge 25 + 15 = 40, new array: {40, 99}
- left = 2, right = 1 → loop ends
Output:
2 merge operations
Example 2:
Input:
arr[] = {3, 2, 2, 3}
Output:
0
Explanation:
The array is already a palindrome, as the first and last elements are the same (3), and the second and third elements are also the same (2). So, no merge operation is needed.
Algorithm for the Example:
1. Initialize two pointers: left = 0, right = n – 1.
2. While left < right:
- If arr[left] == arr[right], move both pointers inward.
- If arr[left] < arr[right], merge arr[left] and arr[left + 1], increase merge count, and move left pointer.
- If arr[left] > arr[right], merge arr[right – 1] and arr[right], increase merge count, and move right pointer.
3. Repeat until the array becomes a palindrome.
4. Return the total number of merge operations.
Since the array {3, 2, 2, 3} is already a palindrome, the algorithm will simply move the pointers inward and return 0 operations.
C++ Code for the Example 2:
#include <iostream>
using namespace std;
int minMergeOperations(int arr[], int n) {
int left = 0, right = n - 1;
int count = 0;
while (left < right) {
if (arr[left] == arr[right]) {
left++;
right--;
} else if (arr[left] < arr[right]) {
arr[left + 1] += arr[left];
left++;
count++;
} else {
arr[right - 1] += arr[right];
right--;
count++;
}
}
return count;
}
int main() {
int arr[] = {3, 2, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum merge operations: " << minMergeOperations(arr, n) << endl;
return 0;
}Output:
Minimum merge operations: 0
Why Use the Two-Pointer Approach?
The two-pointer approach is optimal for this problem because:
- We need to compare both ends of the array.
- Palindromes are symmetric.
- It allows in-place comparison and merging efficiently.
Key Takeaways:
- A merge operation adds two adjacent elements.
- Try to keep the structure symmetric by comparing from both ends.
- Use the two-pointer method for efficiency.
- Practice with different test cases to build strong insight.
Conclusion
To make an array a palindrome with the least effort, we use the two-pointer approach and merge adjacent elements when needed. This helps reduce the number of operations while keeping the array balanced. It’s a useful problem to understand array manipulation, two-pointer logic, and optimizing operations — all important concepts in coding interviews.
FAQs
Making an array palindrome means transforming it so that it reads the same forwards and backwards. Merge operations involve combining two adjacent elements into their sum, effectively reducing the array’s length by one at each operation until the array becomes palindromic.
The most efficient strategy uses a two-pointer approach: start one pointer at the beginning and the other at the end of the array. If the elements at both pointers are equal, move both inward. If not, merge the smaller value with its neighbor (either on the left or right), increment the operation count, and continue until the pointers meet or cross.
The optimal solution runs in linear time, O(n), since each element is considered at most once as the pointers move toward each other. The space complexity is O(1) because only a few variables are needed for pointers and counting operations.
Yes, both recursive and iterative solutions are possible. The recursive solution checks base cases (when pointers meet or cross), then decides whether to merge on the left or right or move both pointers inward, and recurses accordingly. The iterative solution typically uses a while loop with two pointers.
Common pitfalls include not handling arrays with all identical elements (which require zero merges), arrays of length one (already palindromic), or failing to correctly update pointers and the array when merging. It’s also important to avoid unnecessary merges and ensure the algorithm always chooses the minimal merge path.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
