Contents

**Weird Palindrome Making MAKEPAL Solution**

Naveej is from a tribe that speaks some weird language their alphabet consists of N distinct characters. He has an array A=[A1,A2,…,AN], where Ai denotes the number of occurrences of the i-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 i (1≤i≤N) and convert all occurrences of i-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=2 and A=[2,2] and we consider the characters to be a and b, he can make both abba and baab, but aba is not allowed because it uses only 3 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 T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N the size of the alphabet.
- The second line contains N space-separated integers: A1,A2,…,AN, where Ai is the number of occurrences of the i-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≤1000
- 1≤N≤2⋅105
- 1≤Ai≤109
- It is guaranteed that the sum of N over all test cases does not exceed 2⋅105

**Subtasks**

**Subtask 1 (100 points):**Original constraints

**Sample Input 1**

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

**Sample Output 1**

```
0
1
```

**Explanation**

- In the first test case, N=1. Let the character be a. We can make the following palindromic string: aaaa.
- In the second test case, N=3. Let the characters be a, b, c. 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 b to c. Then, we can make the following palindromic string: acaccaca.

**SOLUTION**

*Program Python:*** Weird Palindrome Making MAKEPAL Solution** in Python

```
# 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() {
// your code goes here
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
{
// your code goes here
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);
}
}
}
```

*November Long Challenge 2021 Solution*

*November Long Challenge 2021 Solution*

*Which Fuel is Cheaper CHEAPFUEL Solution**Convex Hulk CONHULK Solution**Functional Array FUNARR Solution**Flip or Compress FLIPCOMP Solution**Maximise the bridges MAXBRIDGE Solution**Wildcard Replacement WLDRPL Solution**Xor Equation XOREQN Solution**Hill Sequence HILLSEQ Solution**Weird Palindrome Making MAKEPAL Solution**Equal Coins EQUALCOIN Solution Codechef*

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))

We appreciate your solution submission we have added your solution on the post with credit, if possible please leave your codechef profile link to tag you.