Given an array A of size N. Find the minimum number of operations needed to convert the given array to 'Palindromic Array'.
The only allowed operation is that you can merge two adjacent elements in the array and replace them with their sum.
Input array: 5 3 3 3 No of minimum operation: 3 (don't worry, you will know the reason soon!!) Input array: 5 3 3 5 No of minimum operation: 0 (It's palindromic array!!)
What is palindromic array?
An array is known to palindromic if it forms a palindrome with all its elements.
What are the operations allowed to form a palindromic array from any input array?
The only operation allowed is to merge two adjacent elements and replacing them with their sum.
Can we convert any input array to a palindromic array?
Yah, we can convert any input array to a palindromic array since an array with a single element is always a palindromic array. Thus, any input array can ultimately lead to a palindromic array.
For solving the above problem a recursive algorithm can be constructed based on the following conditions.
Let array [i, j] be the subarray to be checked where I be the staring index & j be the end index
So there can be three cases,
Based on these three conditions we have constructed the recursive function:
Example with explanation:
Outputneed an explanation for this answer? contact us directly to get an explanation for this answer