Make It Palindrome

Easy
0/40
Average time to solve is 25m
profile
Contributed by
47 upvotes
Asked in companies
AmazonSAP LabsNagarro Software

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input-1
2
3
1 2 1
5
1 2 3 4 1
Sample Output-1
0
2
Explanation for Sample Input 1:
For test case 1:
    The given array is already a palindrome. Hence the answer is 0.
For test case 2:
    We select indexes 3 and 4 to merge. The array will look like [1, 2, 7, 1].
    We select indexes 2 and 3 to merge. The array will look like [1, 9, 1].
    Now the array is a palindrome. Hence the answer will be 2.
Sample Input -2
2
1
8
3
1 3 3
Sample Output -2
0
2
Hint

Merge the indexes when required.

Approaches (1)
Greedy

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’.
Time Complexity

O(N). Where ‘N’ is the length of the array.

The combined movement of both of the pointers will be ‘N’. Hence the overall complexity is O(N).

Space Complexity

O(1).

We are creating five variables. Hence the overall complexity is O(1).

Code Solution
(100% EXP penalty)
Make It Palindrome
Full screen
Console