# Weird Palindrome Making MAKEPAL Solution Codechef

Page Contents

## Weird Palindrome Making MAKEPAL Solution

Naveej is from a tribe that speaks some weird language – their alphabet consists of NN distinct characters. He has an array A=[A1,A2,…,AN]A=[A1,A2,…,AN], where AiAi denotes the number of occurrences of the ii-th character with him.

He wants to make a palindromic string using all the characters he has (every character he has must be used in this string).

In order to make this possible, he can perform the following operation:

• Select an ii (1≤i≤N)(1≤i≤N) and convert all occurrences of ii-th alphabet to any other alphabet of his choice.

Note that Naveej just wants to be able to make any palindrome, as long as every character is used. For example, if N=2N=2 and A=[2,2]A=[2,2] and we consider the characters to be aa and bb, he can make both abbaabba and baabbaab, but abaaba is not allowed because it uses only 33 characters.

Find the minimum number of operations required such that Naveej can make a palindromic string using all the characters he has. It can be proven that there always exists at least one sequence of operations allowing for the formation of a palindrome.

### Input Format

• The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN – the size of the alphabet.
• The second line contains NN space-separated integers: A1,A2,…,ANA1,A2,…,AN, where AiAi is the number of occurrences of the ii-th character with Naveej.

### Output Format

For each test case, output a single line containing one integer – the minimum number of operations required so that Naveej can make a palindromic string using all the characters he has.

### Constraints

• 1≤T≤10001≤T≤1000
• 1≤N≤2⋅1051≤N≤2⋅105
• 1≤Ai≤1091≤Ai≤109
• It is guaranteed that the sum of NN over all test cases does not exceed 2⋅1052⋅105

• Subtask 1 (100 points): Original constraints

```2
1
4
3
4 3 1
```

```0
1
```

### Explanation

• In the first test case, N=1N=1. Let the character be aa. We can make the following palindromic string: aaaaaaaa.
• In the second test case, N=3N=3. Let the characters be aa, bb, cc. It is initially not possible to make a palindrome with the given occurrences of the characters. We perform 1 operation: Convert all the occurrences of bb to cc. Then, we can make the following palindromic string: acaccacaacaccaca.

Weird Palindrome Making MAKEPAL Solution is updated. Click Below

## SOLUTION

Program Python: Weird Palindrome Making MAKEPAL Solution in Python

Code Credit: tashi (in comment section)

```# cook your dish here
T = int(input())
for i in range(0,T):
N = int(input())
A = [int(x) for x in input().split()]
if N==1:
print(0)
else:
v =[]
for i in A:
if i in range(1,1000000000,2):
v.append(i)
if len(v)==1:
print(0)
elif len(v)%2== 0:
print(int(len(v)/2))
else:
print(int((len(v)-1)/2))```

Program C++: Weird Palindrome Making MAKEPAL Solution in C++

```#include <iostream>
using namespace std;

int main() {
int t,n,i,x;
scanf("%d",&t);
while(t--)
{
int c=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&x);
if (x%2==1)
{
c++;
}
}
if (c%2==1)
{
c--;
}
printf("%d\n",c/2);
}
return 0;
}
```

Program Java: Weird Palindrome Making MAKEPAL Solution in Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc= new Scanner(System.in);
int t=sc.nextInt();
int i;
while(t-- >0)
{
int c=0;
int n=sc.nextInt();
for(i=0;i<n;i++)
{
int x=sc.nextInt();
if (x%2==1)
{
c++;
}
}
if (c%2==1)
{
c--;
}
System.out.println(c/2);
}
}
}
```

## Codechef Long ChallengesSolution

### 2 thoughts on “Weird Palindrome Making MAKEPAL Solution Codechef”

1. T = int(input(“T”))
for i in range(0,T):
N = int(input(“N”))
A = [int(x) for x in input(“A”).split()]
if N==1:
print(0)
else:
v =[]
for i in A:
if i in range(1,1000000000,2):
v.append(i)
if len(v)==1:
print(0)
elif len(v)%2== 0:
print(int(len(v)/2))
else:
print(int((len(v)-1)/2))

• 