Last Updated: 9 Dec, 2021

Make It Palindrome

Easy

Asked in companies

Solve now

Problem statement

You are given an array ‘A’ of length ‘N’ consisting only of positive integers. Your task is to make the given array a palindrome by using a minimum number of operations. In one operation, you can select two adjacent indexes and merge them by adding their values. After every operation, the length of the array decreases by one.

Note: An array of length ‘1’ is a palindrome.

For example:

Let’s say the array ‘A’ = [1, 2, 3, 4, 5], then after merging indexes 2 and 3, the array ‘A’ will look like [1, 5, 4, 5].

Input Format-

First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’, denoting the length of the array ‘A’.
The following line contains ‘N’ space-separated positive integers, representing the array’s values.

Output Format-

For each test case, you have to print an integer denoting the minimum number of operations required to turn the given array into a palindrome.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints -

1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5 
1 <= A[i] <= 10^9, for 1 <= i <= ‘N’
Note- Sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: We will maintain two pointers, ‘i’ and ‘j’, representing the two endpoints, if A[i] == A[j], then the minimum operations required will be equal to minimum operations required to make subarray A[(i +1)….(j - 1)] a palindrome, else we will merge index ‘i’ and ‘i + 1’ if A[i] < A[j] else we merge index ‘j’ and ‘j - 1’. This work because if we merge the larger values, then their values will increase even more, but if we merge the smaller value, then there is a possibility that it will become equal to the larger value.

Algorithm:

Create three variables, ‘i’, ‘j’ and ‘ans’, and initialize them to 0, ‘N - 1’ and 0, respectively.
Create two variables, ‘left’ and ‘right’ and initialize them to A[0] and A[N - 1], respectively.
While i < j.
If left == right.
Increment ‘i’ by 1.
Decrement ‘j’ by 1.
Update ‘left’ to A[i].
Update ‘right’ to A[j].
Else if left < right.
Increment ‘ans’ by 1.
Update ‘left’ to A[i + 1] + ‘left’.
Increment ‘i’ by 1.
Else.
Increment ‘ans’ by 1.
Update ‘right’ to A[j - 1] + ‘right’.
Decrement ‘j’ by 1.
Print ‘ans’.

Solve now